CF2267F2.XOR Transformations (Hard Version)

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.

这是该问题的困难版本。两个版本的区别在于，本版本中 $n$ 和 $q$ 的约束更大。仅当您已解决该问题的所有版本后，才可进行 Hack。

对于一个由 $m$ 个整数组成的数组 $b$，定义如下变换：

• 写出所有满足 $1 \le i < j \le m$ 的 $b_i \oplus b_j$ 的值，其中 $\oplus$ 表示按位异或（XOR）运算；
• 取出所写出的值中最小的 $m$ 个；
• 将数组的元素替换为这 $m$ 个选出的值。

例如，考虑对数组 $[6, 7, 8, 9, 15]$ 进行变换：我们写出所有值 $1, 1, 6, 7, 8, 9, 14, 14, 15, 15$。变换后，数组变为 $[1, 1, 6, 7, 8]$ —— 即其中最小的 $5$ 个元素。

给定一个由 $n$ 个非负整数组成的数组 $a$。记 $\max(a)$ 为数组 $a$ 的最大值，$\min(a)$ 为其最小值。您的任务是回答 $q$ 个查询，每个查询给出一个整数 $x$。对每个查询，请计算对数组 $a$ 执行 $x$ 次上述变换后 $\max(a) - \min(a)$ 的值。注意，各查询相互独立，即每次查询前，数组 $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 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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$5\le n\le 10^5, 1\le q\le 10^5$）——分别表示数组的大小和查询次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\le a_i\lt 2^{30}$）。

每个测试用例接下来的 $q$ 行，每行包含一个整数 $x$（$0\le x\lt 2^{30}$）。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $10^5$。

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

对于每个测试用例，输出 $q$ 个整数——即每个查询的答案。

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

在第一个测试用例中，经过一次变换后，数组变为 $[0, 0, 0, 0, 1]$。此时 $\max(a) - \min(a) = 1 - 0 = 1$。

在第二个测试用例中，初始数组为 $[6, 7, 8, 9, 15]$。初始时，$\max(a) - \min(a) = 15 - 6 = 9$。变换后，数组变为 $[1, 1, 6, 7, 8]$，此时 $\max(a) - \min(a) = 8 - 1 = 7$。