给你 $$$n$$$ 对象。每个对象都有两个整数属性:$$$val_i$$$——它的价格——和$$$mask_i$$$。保证所有价格的总和最初不为零。
您想要选择一个正整数$$$s$$$。之后所有对象都将被修改。将使用以下过程修改第 $$$i$$$ 对象:
- 考虑二进制表示法中的 $$$mask_i$$$ 和 $$$s$$$,
- 计算 $$$s$$$ 和 $$$mask_i$$$ 的按位 AND ($$$s \,\&\, mask_i$$$),
- 如果 ($$$s \,\&\, mask_i$$$) 包含奇数个,则将 $$$val_i$$$ 替换为 $$$-val_i$$$。否则,对第 $$$i$$$ 个对象不执行任何操作。
你需要找到这样一个整数$$$s$$$,当上面的修改完成后,所有价格的总和改变符号(如果是负数,它应该变成正数,反之亦然;不允许它变成零)。总和的绝对值可以是任意的。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 对象的数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含整数 $$$val_i$$$ 和 $$$mask_i$$$ ($$$-10^9 \leq val_i \leq 10^9$$$, $$$1 \le mask_i \le 2^{62} - 1$$$) — 对象及其掩码的价格。
保证 $$$val_i$$$ 的总和最初不为零。
输出
打印一个整数 $$$s$$$ ($$$1 \le s \le 2^{62} - 1$$$),这样如果我们如上所述修改对象,$$$val_i$$$ 的总和的符号会改变它的符号。
如果有多个这样的$$$s$$$,则打印其中的任何一个。可以证明总是至少有一个有效的$$$s$$$。
示例
输入 #1
5 17 206 -6 117 -2 151 9 93 6 117
输出 #1
64
输入 #2
1 1 1
输出 #2
1
注意
在第一个测试示例中,除了带有掩码 $$$151$$$ 的对象外,所有对象都会更改其价格。
因此,它们的总和将改变其符号:最初为 $$$24$$$,修改后 — $$$-28$$$。
在第二个测试示例中,唯一的对象将更改其价格。因此总和将改变其符号。