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.