CF1148F Foo Fighters

给定 $n$ 个物品。每个物品有两个整数属性：$val_i$（其价格）和 $mask_i$。保证所有价格的总和初始时不为零。 你需要选择一个正整数 $s$。所有物品随后会被如下方式修改： - 将 $mask_i$ 和 $s$ 都看作二进制表示， - 计算 $s$ 与 $mask_i$ 的按位与（即 $s\,\&\,mask_i$）， - 如果 $s\,\&\,mask_i$ 的二进制表示中有奇数个 $1$，则将 $val_i$ 替换为 $-val_i$；否则 $val_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$），分别表示第 $i$ 个物品的价格和掩码。 保证所有 $val_i$ 的总和初始时不为零。

输出一个整数 $s$（$1 \leq s \leq 2^{62} - 1$），使得经过上述修改后，所有 $val_i$ 的总和改变符号。 如果有多个满足条件的 $s$，输出任意一个即可。可以证明一定存在至少一个合法的 $s$。

在第一个样例中，除了掩码为 $151$ 的物品外，所有物品的价格都会改变符号。 因此它们的总和会改变符号：初始为 $24$，修改后为 $-28$。 在第二个样例中，唯一的物品会改变价格，因此总和会改变符号。 由 ChatGPT 4.1 翻译