Foo Fighters

题意翻译

你有 $n$ 个物品,每个物品有两个权值 $val$ 和 $mask$ 。 你可以选择一个数 $s$ ,然后修改所有数的 $val$ ,如果 $s\ \&\ mask$ 有奇数个 $1$ 就把 $val$ 变成 $-val$ 。 输出一个 $s$ ,使得权值和符号变反。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#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.

输入输出格式

输入格式


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.

输出格式


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 $ .

输入输出样例

输入样例 #1


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

输出样例 #1


64

输入样例 #2


1
1 1

输出样例 #2


1

说明

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.