题目描述

大鱼吃小鱼，小鱼吃虾米

在一条清澈的河流中，游弋着 $n$ 条鱼，第 $i$ 条鱼的体重为 $w_i$。如果$w_i \ge w_j$，鱼$i$能够吃掉鱼$j$，被吃掉的鱼会消失，吞食者的体重变为两者体重的按位异或（$w_i \oplus w_j$）。

钓鱼的渔夫十分无聊，他想做一个参数为 $x$ 的实验，过程如下：

1. 在河流最右端（第 $n$ 条鱼之后）加入一条新鱼，体重为 $x$。
2. 如果这条新鱼的体重不小于左侧相邻鱼的体重，则它会吞食该鱼并取代它的位置（向左移动一格）；其体重变为两条鱼体重的按位异或，重复此过程，直到左侧没有鱼或左侧鱼的体重严格大于它自身（在此过程中，其他的鱼不会自相残杀，即其他的鱼都不会被吃掉）。
3. 本次实验的得分定义为被吃掉的鱼的总数量。

渔夫给你了 $q$ 次询问，每次给你一个整数 $x$，请输出参数为$x$的实验的得分。

注意：渔夫并不希望实验真的进行（鱼都被吃了他钓什么），他只是问假设能得多少分，换句话说，询问是不持久的。

输入格式

第一行为一个正整数$T(1 \le T \le 10^4)$，测试用例的数量
对于每个测试用例：第一行为两个整数$n, q(1 \le n, q \le 2 \times 10^5)$，分别表示鱼的数量和询问的数量。
下一行包含$n$个整数$w_1, w_2,...,w_n(1 \le w_i \le 2^{30})$，表示鱼的重量
接下来$q$行，一行一个整数$x(1 \le x \le 2^{30})$，实验参数

题目保证：所有的测试数据中，$n$的总和不超过$2 \times 10^5$，$q$的总和不超过$2 \times 10^5$。

输出格式

每组测试用例占一行。

对于每个询问，输出一个整数：实验得分，不同询问之间以空格分隔。

样例

3
1 1
5
6
4 4
1 5 4 11
8
13
16
15
10 9
10 4 3 9 7 4 6 1 9 4
2
6
5
6
9
8
6
2
7

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$ 的分数结束了整个过程。