给定您 $$$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$$$。
示例
输入复制
42 15 793 19 9 8246 41 1 4 5 1 4102030401 100
输出复制
1731116310
注意
在第一个测试用例中,我们花费$$$1$$$硬币将$$$a_2$$$增加$$$1$$$,产生序列$$$[5,8]$$$。合适的$$$b$$$ 是$$$[1,8]$$$。可以证明,一个人不能花费少于 $$$1$$$ 的硬币来实现这一目标。
在第二个测试用例中,我们可以花费$$$7$$$硬币将$$$a_1$$$增加$$$7$$$,从而得到序列$$$[16,9,8]$$$。合适的 $$$b$$$ 是 $$$[16,9,1]$$$。