当前没有测试数据。

题目描述

这是本题的简单版本。两个版本的区别在于本版本中 $n$ 和 $q$ 的约束更小。只有当你解决了本题的所有版本时，才能进行 hack。

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

• 写出所有满足 $1\le i<j\le m$ 的 $b_i\oplus b_j$ 的值，其中 $\oplus$ 代表按位异或运算。
• 取出这些值里最小的 $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$。对每个询问，求对原数组执行 $x$ 次变换之后，$\max(a)-\min(a)$ 的值。注意询问之间相互独立：每次询问前，数组 $a$ 都会恢复成初始状态。

输入格式

每个测试点包含多组测试用例。第一行一个整数 $t$（$1 \le t \le 100$），代表测试用例数量。接下来是每组测试用例的描述。

每组测试用例第一行两个整数 $n,q$（$5\le n\le 2000, 1\le q\le 2000$）——数组长度和询问次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<2^{30}$）。

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

保证所有测试用例的 $n$ 之和、$q$ 之和都不超过 $2000$。

输出格式

对每组测试用例，输出 $q$ 个整数——每个询问对应的答案。

4
5 1
0 0 1 1 1
1
5 2
6 7 8 9 15
0
1
8 2
102 92 15 19 25 54 62 36
2
1
10 1
56 73 81 23 17 92 50 34 67 78
2

1
9
7
12
31
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$。

原题链接

原题链接