#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))


long long gcd(long long a, long long b) {
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}
//a x + b y = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

long long InvMod(long long a, long long mod) {
  long long x, y;
  if (extgcd(a, mod, x, y) == 1) { return (x + mod) % mod; }
  return 0;
}


ll Mul(ll base, ll power, ll mod) {
  ll ret = 0;
  while (power > 0) {
    if (power & 1) { ret = (ret + base) % mod; }
    base = (base + base) % mod;
    power >>= 1;
  }
  assert(0 <= ret && ret < mod);
  return ret;
}
// need extgcd
ll ChineseRemainderTherom(const vector<ll> &anss, const vector<ll> &mods) {
  assert(anss.size() == mods.size());
  ll all = 1;
  for (int i = 0; i < (int)mods.size(); i++) {
    all *= mods[i];
  }
  ll ret = 0;
  for (int i = 0; i < (int)anss.size(); i++) {
    ll x, y;
    extgcd(mods[i], all / mods[i], x, y); 
    y = (y + all) % all;
    ret = (ret + Mul(Mul((anss[i] + all) % all, y, all), (all / mods[i]), all)) % all;
    //assert(ret >= 0); 
  }
  return ret;
}


int psize;
int prime[2];

int op[100010];
int y[100010];

int main() {
  int n;
  prime[psize++] = 797987;
  prime[psize++] = 798121;
  while (scanf("%d", &n) > 0) {
    REP(i, n) {
      scanf("%d %d", &op[i], &y[i]);
    }
    ll all = 1;
    vector<ll> ans;
    vector<ll> mod;
    REP(iter, psize) {
      all *= prime[iter];
      mod.push_back(prime[iter]);
      ll MOD = prime[iter];
      ll v = 0;
      REP(i, n) {
        if (op[i] == 1) {
          v = ((v + y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 2) {
          v = ((v - y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 3) {
          v = ((v * y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 4) {
          if (y[i] < 0) {
            v = (v * InvMod(-y[i], MOD)) % MOD;
            v = ((v * -1) % MOD + MOD) % MOD;
          } else {
            v = (v * InvMod(y[i], MOD)) % MOD;
          }
        }
      }
      ans.push_back(v);
    }
    ll v = ChineseRemainderTherom(ans, mod);
    if (v > (1LL << 31)) {
      v -= all;
    }
    printf("%lld\n", v);
  }
}
### Prompt

Please formulate a Cpp solution to the following problem:

Problem statement

There is a rational number sequence $ X_0, X_1, X_2, ..., X_N $. Each term is defined as follows.


1. $ X_0 = 0 $
2. $ X_i = X_ {i-1} $ $ op_i $ $ Y_i $ ($ 1 \ leq i \ leq N $). However, $ op_i $ is $ + $, $ − $, $ × $, $ ÷ $ Either.



Find $ X_N $.

Constraint

* $ 1 \ leq N \ leq 10 ^ 5 $
* $ 1 \ leq o_i \ leq 4 $
* $ -10 ^ 6 \ leq Y_i \ leq 10 ^ 6 $
* If $ o_i = 4 $, then $ Y_i \ neq 0 $
* $ X_N $ is an integer greater than or equal to $ -2 ^ {31} $ and less than $ 2 ^ {31} $.



input

Input follows the following format. All given numbers are integers.


$ N $
$ o_1 $ $ Y_1 $
$ o_2 $ $ Y_2 $
$ ... $
$ o_N $ $ Y_N $

When $ o_i = 1 $, $ op_i $ is +, when $ o_i = 2 $, $ op_i $ is −, when $ o_i = 3 $, $ op_i $ is ×, and when $ o_i = 4 $, $ op_i $ is ÷.

output

Print the value of $ X_N $ on one line.

Example

Input

4
1 1
4 2
2 4
3 4


Output

-14

### Response

```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))


long long gcd(long long a, long long b) {
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}
//a x + b y = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

long long InvMod(long long a, long long mod) {
  long long x, y;
  if (extgcd(a, mod, x, y) == 1) { return (x + mod) % mod; }
  return 0;
}


ll Mul(ll base, ll power, ll mod) {
  ll ret = 0;
  while (power > 0) {
    if (power & 1) { ret = (ret + base) % mod; }
    base = (base + base) % mod;
    power >>= 1;
  }
  assert(0 <= ret && ret < mod);
  return ret;
}
// need extgcd
ll ChineseRemainderTherom(const vector<ll> &anss, const vector<ll> &mods) {
  assert(anss.size() == mods.size());
  ll all = 1;
  for (int i = 0; i < (int)mods.size(); i++) {
    all *= mods[i];
  }
  ll ret = 0;
  for (int i = 0; i < (int)anss.size(); i++) {
    ll x, y;
    extgcd(mods[i], all / mods[i], x, y); 
    y = (y + all) % all;
    ret = (ret + Mul(Mul((anss[i] + all) % all, y, all), (all / mods[i]), all)) % all;
    //assert(ret >= 0); 
  }
  return ret;
}


int psize;
int prime[2];

int op[100010];
int y[100010];

int main() {
  int n;
  prime[psize++] = 797987;
  prime[psize++] = 798121;
  while (scanf("%d", &n) > 0) {
    REP(i, n) {
      scanf("%d %d", &op[i], &y[i]);
    }
    ll all = 1;
    vector<ll> ans;
    vector<ll> mod;
    REP(iter, psize) {
      all *= prime[iter];
      mod.push_back(prime[iter]);
      ll MOD = prime[iter];
      ll v = 0;
      REP(i, n) {
        if (op[i] == 1) {
          v = ((v + y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 2) {
          v = ((v - y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 3) {
          v = ((v * y[i]) % MOD + MOD) % MOD;
        } else if (op[i] == 4) {
          if (y[i] < 0) {
            v = (v * InvMod(-y[i], MOD)) % MOD;
            v = ((v * -1) % MOD + MOD) % MOD;
          } else {
            v = (v * InvMod(y[i], MOD)) % MOD;
          }
        }
      }
      ans.push_back(v);
    }
    ll v = ChineseRemainderTherom(ans, mod);
    if (v > (1LL << 31)) {
      v -= all;
    }
    printf("%lld\n", v);
  }
}
```