CF2165C.Binary Wine

You are given $n$ integers $a_1,a_2,\ldots,a_n$ within the range $[0,2^{30})$.

You can spend $1$ coin to increase any $a_i$ by $1$. You can perform this operation any number of times.

You need to solve $q$ queries; for each query, you are given an integer $c$, also in the range $[0,2^{30})$. You would like it if there exists a sequence $b$ of length $n$ with the following properties:

• For every $1\le i\le n$, $0\le b_i\le a_i$.
• $b_1\oplus b_2\oplus\ldots\oplus b_n=c$, where $\oplus$ denotes the bitwise XOR operation.

Please calculate the minimum number of coins you will have to spend, such that there exists a suitable $b$.

The queries are independent, meaning that any operations you perform on the sequence $a$ will not impact future queries.

给你 $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$ 所做的任何操作均不会影响后续查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case consists of two integers $n,q$ ($1\le n\le5\cdot10^5$, $1\le q\le5\cdot10^4$) — the length of sequence $a$ and the number of queries.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i \lt 2^{30}$) — the initial sequence $a$.

Each of the next $q$ lines contains a single integer $c$ ($0\le c \lt 2^{30}$) — the target XOR.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $5\cdot10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each query, output a single integer — the minimum coins you will have to spend, such that there exists a suitable $b$.

对于每个查询，输出一个整数——即满足存在合适的 $b$ 时，你所需花费的最少硬币数。

In the first test case, we spend $1$ coin to increase $a_2$ by $1$, resulting in sequence $[5,8]$. A suitable $b$ would be $[1,8]$. It can be shown one cannot spend less than $1$ coin to achieve the objective.

In the second test case, we can spend $7$ coins to increase $a_1$ by $7$, resulting in sequence $[16,9,8]$. A suitable $b$ would be $[16,9,1]$.

在第一个测试用例中，我们花费 $1$ 枚硬币将 $a_2$ 增加 $1$，得到序列 $[5,8]$。一个合适的 $b$ 序列可以是 $[1,8]$。可以证明，无法花费少于 $1$ 枚硬币来实现目标。

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