给定一个含有 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$ 以及 $q$ 次询问。对于每次给定参数 $k$ 的询问，确定最多可以组成多少个互不相交的数对 $(i, j)$（$i \neq j$），使得 $a_i + a_j \le k$。每个元素最多只能用于一个数对中。

你需要在线回答询问。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$) —— 测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^4$, $1 \le q \le 5 \cdot 10^5$) —— 数组元素个数和询问次数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$)。

• 接下来的 $q$ 行，每行包含一个整数 $k'$ ($0 \le k' < 2^{31}$)，表示一次询问。实际的询问参数 $k$ 应按如下方式计算：$k = k' \oplus \text{last\_ans}$ ($0 \le k < 2^{31}$)，其中：

  • $\oplus$ 表示按位异或运算。
  • $\text{last\_ans}$ 是上一次询问的答案（初始时为 0）。

保证所有测试数据的 $n$ 之和不超过 $10^4$，且所有测试数据的 $q$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每组测试数据，输出 $q$ 行 —— 按输入顺序依次对应每次询问的答案。

样例

输入样例 1

2
5 6
1 3 7 9 12
5
7
6
9
8
11
6 4
7 12 15 19 22 27
27
28
35
38

输出样例 1

1
1
1
1
1
2
2
2
2
3

说明

两组测试数据的实际询问参数 $k$ 分别为 $[5, 6, 7, 8, 9, 10]$ 和 $[27, 30, 33, 36]$。