This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $n$ and $q$ are higher. You can make hacks only if you have solved all versions of this problem.

For an array $b$ consisting of $m$ integers, define a transformation as follows:

• Write down the values $b_i\oplus b_j$ for all $1\le i\lt j\le m$, where $\oplus$ denotes the bitwise XOR operation.
• Take the $m$ smallest among the written values.
• Replace the elements of the array with the taken $m$ values.

For example, consider the transformation of the array $[6, 7, 8, 9, 15]$. We write down the values $1, 1, 6, 7, 8, 9, 14, 14, 15, 15$. After the transformation, the array becomes $[1, 1, 6, 7, 8]$ — the $5$ smallest elements.

You are given an array $a$ consisting of $n$ non-negative integers. Let $\max(a)$ denote the maximum element of the array $a$, and $\min(a)$ — the minimum. Your task is to answer $q$ queries, each of which gives you one integer $x$. For each query, find the value of $\max(a) - \min(a)$ after $x$ transformations on the array. Note that the queries are independent, i.e. before each query, the array $a$ is restored to its original state.

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 contains two integers $n$ and $q$ ($5\le n\le 10^5, 1\le q\le 10^5$) — the size of the array 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 next $q$ lines of each test case contain an integer $x$ ($0\le x\lt 2^{30}$).

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$.

Output

For each test case, print $q$ integers — the answer to each query.

Note

In the first test case, after one transformation, the array becomes $[0, 0, 0, 0, 1]$. Here $\max(a) - \min(a) = 1 - 0 = 1$.

In the second test case, the initial array is $[6, 7, 8, 9, 15]$. Initially, $\max(a) - \min(a) = 15 - 6 = 9$. After the transformation, the array becomes $[1, 1, 6, 7, 8]$, where $\max(a) - \min(a) = 8 - 1 = 7$.