← 返回题目列表

Codeforces · 2165/C

C. 二元酒

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

给定您 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$,范围为 $$$[0,2^{30})$$$。

您可以花费$$$1$$$硬币将任何$$$a_i$$$增加$$$1$$$。您可以多次执行此操作。

您需要解决 $$$q$$$ 查询;对于每个查询,您都会获得一个整数 $$$c$$$,也在 $$$[0,2^{30})$$$ 范围内。如果存在长度为 $$$n$$$ 且具有以下属性的序列 $$$b$$$,您会希望它:

  • 对于每个 $$$1\le i\le n$$$,$$$0\le b_i\le a_i$$$。
  • $$$b_1\oplus b_2\oplus\ldots\oplus b_n=c$$$,其中 $$$\oplus$$$ 表示按位异或运算。

请计算您需要花费的最少硬币数量,以便存在合适的$$$b$$$。

查询是 独立,这意味着您对序列 $$$a$$$ 执行的任何操作都不会影响将来的查询。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行由两个整数 $$$n,q$$$ ($$$1\le n\le5\cdot10^5$$$, $$$1\le q\le5\cdot10^4$$$) 组成 - 序列 $$$a$$$ 的长度和查询的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \lt 2^{30}$$$) - 初始序列 $$$a$$$。

接下来的 $$$q$$$ 行都包含一个整数 $$$c$$$ ($$$0\le c \lt 2^{30}$$$) — 目标异或。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$5\cdot10^4$$$。

输出

对于每个查询,输出一个整数 - 您必须花费的最少硬币,以便存在合适的 $$$b$$$。

示例

输入
复制

4
2 1
5 7
9
3 1
9 9 8
24
6 4
1 1 4 5 1 4
10
20
30
40
1 1
0
0

输出
复制

1
7
3
11
16
31
0

注意

在第一个测试用例中,我们花费$$$1$$$硬币将$$$a_2$$$增加$$$1$$$,产生序列$$$[5,8]$$$。合适的$$$b$$$ 是$$$[1,8]$$$。可以证明,一个人不能花费少于 $$$1$$$ 的硬币来实现这一目标。

在第二个测试用例中,我们可以花费$$$7$$$硬币将$$$a_1$$$增加$$$7$$$,从而得到序列$$$[16,9,8]$$$。合适的 $$$b$$$ 是 $$$[16,9,1]$$$。