一条线上有 $$$n$$$ 个史莱姆,其中第 $$$i$$$ 的重量为 $$$w_i$$$。史莱姆 $$$i$$$ 能够吃掉另一个史莱姆 $$$j$$$ 如果 $$$w_i \geq w_j$$$;之后,史莱姆 $$$j$$$ 消失,史莱姆 $$$i$$$ 的重量变为 $$$w_i \oplus w_j$$$$$^{\text{*}}$$$。
史莱姆之王想要经营一家 参数实验 $$$x$$$ 如下:
- 将重量为 $$$x$$$ 的新史莱姆添加到该行的右端(在第 $$$n$$$ 个史莱姆之后)。
- 如果可以的话,这个新史莱姆会吃掉它左边的史莱姆,然后取代它的位置(向左移动一位)。它将继续这样做,直到其左侧没有粘液或左侧粘液的重量大于其自身重量。 (在此过程中不会吃掉其他史莱姆。)
- 的 分数 本实验的 是吃掉的史莱姆总数。
史莱姆之王将向您询问 $$$q$$$ 问题。在每个查询中,您将获得一个整数$$$x$$$,并且您需要通过参数$$$x$$$确定实验的分数。
请注意,国王并不希望你实际执行每个实验;他的史莱姆会死,这并不理想。他只是问假设的分数是多少;换句话说,查询是 不 执着。
$$$^{\text{*}}$$$这里$$$\oplus$$$表示按位异或运算。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 分别是史莱姆的数量和查询的数量。
以下行包含 $$$n$$$ 整数 $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \lt 2^{30}$$$) — 史莱姆的重量。
以下 $$$q$$$ 行包含单个整数 $$$x$$$ ($$$1 \le x \lt 2^{30}$$$) — 实验参数。
在所有测试用例中,$$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$,并且 $$$q$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,输出一个整数——实验的分数。
示例
输入复制
31 1564 41 5 4 11813161510 910 4 3 9 7 4 6 1 9 4265698627
输出复制
1 0 2 4 2 0 1 1 1 3 3 1 0 1
注意
对于第一个查询 第二 测试用例:
- 重量为 $$$8$$$ 的粘液将添加到末尾,因此 $$$w = [1, 5, 4, 11, \color{red}8]$$$。
- 添加的史莱姆比左边的史莱姆重量小,所以它不能吃它,因此在没有吃到得分$$$0$$$的史莱姆后结束该过程。
- 重量为 $$$13$$$ 的粘液将添加到末尾,因此 $$$w = [1, 5, 4, 11, \color{red}{13}]$$$。
- 添加的史莱姆比左边的史莱姆重量更大,所以它会吃掉它。它的重量将变为 $$$13 \oplus 11 = 6$$$。现在$$$w = [1, 5, 4, \color{red}{6}]$$$。
- 添加的史莱姆现在将吃掉其左侧的史莱姆,其重量变为 $$$6 \oplus 4 = 2$$$。现在$$$w = [1, 5, \color{red}{2}]$$$。
- 添加的史莱姆不再能够吃掉其左侧的史莱姆,因此它以 $$$2$$$ 的分数结束该过程。