← 返回题目列表

Codeforces · 1148/F

F. 喷火战机

中文机器翻译题面 查看原题

给你 $$$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$$$。

在第二个测试示例中,唯一的对象将更改其价格。因此总和将改变其符号。