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.

Input

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$.

Output

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

Note

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]$.