Foo Fighters

You are given $n$ objects. Each object has two integer properties: $val_i$ — its price — and $mask_i$. It is guaranteed that the sum of all prices is initially non-zero.

You want to select a positive integer $s$. All objects will be modified after that. The $i$-th object will be modified using the following procedure:

• Consider $mask_i$ and $s$ in binary notation,
• Compute the bitwise AND of $s$ and $mask_i$ ($s \,\&\, mask_i$),
• If ($s \,\&\, mask_i$) contains an odd number of ones, replace the $val_i$ with $-val_i$. Otherwise do nothing with the $i$-th object.

You need to find such an integer $s$ that when the modification above is done the sum of all prices changes sign (if it was negative, it should become positive, and vice-versa; it is not allowed for it to become zero). The absolute value of the sum can be arbitrary.

Input

The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the number of objects.

The $i$-th of next $n$ lines contains integers $val_i$ and $mask_i$ ($-10^9 \leq val_i \leq 10^9$, $1 \le mask_i \le 2^{62} – 1$) — the price of the object and its mask.

It is guaranteed that the sum of $val_i$ is initially non-zero.

Output

Print an integer $s$ ($1 \le s \le 2^{62} – 1$), such that if we modify the objects as described above, the sign of the sum of $val_i$ changes its sign.

If there are multiple such $s$, print any of them. One can show that there is always at least one valid $s$.

Examples

input

5
17 206
-6 117
-2 151
9 93
6 117

output

64

input

1
1 1

output

1

Note

In the first test sample all objects will change their prices except for the object with mask $151$.

So their total sum will change its sign: initially $24$, after modifications — $-28$.

In the second test sample the only object will change its price. So the total sum will change its sign.

Solution:

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
vector<long long> val(n);
vector<long long> mask(n);
vector<int> when(n);
long long total = 0;
for (int i = 0; i < n; i++) {
    cin >> val[i] >> mask[i];
total += val[i];
when[i] = __builtin_ctzll(mask[i]);
}
if (total < 0) {
    for (int i = 0; i < n; i++) {
      val[i] *= -1;
    }
    total *= -1;
  }
  long long s = 0;
  for (int bit = 62; bit >= 0; bit--) {
vector<long long> t(2, 0);
for (int i = 0; i < n; i++) {
      if (when[i] == bit) {
        int cur = __builtin_popcountll(s & mask[i]);
        t[cur % 2] += val[i];
      }
    }
    debug(t);
    if (t[0] > t[1]) {
s |= (1LL << bit);
    }
  }
  cout << s << '\n';
  return 0;
}