题目描述

火星科学家正在探索木星众多卫星之一的“Ganymede”。最近，他们发现了一个古代文明的遗迹。科学家们将一些刻有未知语言文字的石板带回了火星。

他们发现，“Ganymede”的居民使用由两个字母组成的字母表，并且每个单词的长度恰好为 $\ell$ 个字母。因此，科学家们决定将该语言的每个单词表示为一个从 $0$ 到 $2^{\ell} - 1$ 的整数。字母表中的第一个字母对应于该整数的零位，第二个字母对应于一位。

同一个单词在这种语言中可能有多种形式。现在，你需要还原出最初的形式。还原过程如下所述。

定义两个单词之间的距离为这两个单词在有多少个位置上的字母不同。例如，$1001_2$ 和 $1100_2$（二进制）之间的距离为 $2$，因为这两个单词在从左到右数的第二位和第四位上字母不同。进一步地，记单词 $x$ 和 $y$ 之间的距离为 $d(x, y)$。

假设某个单词有 $n$ 种形式，第 $i$ 种形式用整数 $x_i$ 表示。所有的 $x_i$ 不一定互不相同，因为两个不同的形式可能用相同的整数表示。考虑某个单词 $y$，则单词 $y$ 的“接近度”定义为它与所有已知形式的距离之和，即 $\sum_{i=1}^{n} d(x_i, y)$。

最初的形式是指接近度最小的单词 $y$。

你需要帮助科学家们，编写程序，根据所有已知的单词形式，找出最初的形式。注意，最初的形式不一定等于给定的 $n$ 个形式中的任意一个。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $\ell$（$1 \le n \le 100$，$1 \le \ell \le 30$），分别表示单词形式的数量和单词的字母数。

第二行包含 $n$ 个整数 $x_i$（$0 \le x_i \le 2^\ell - 1$），表示单词的各种形式。这些整数不一定互不相同。

输出格式

对于每个测试用例，输出一个整数，表示单词的最初形式，即使得 $\sum_{i=1}^{n} d(x_i, y)$ 最小的 $y$（$0 \le y \le 2^\ell - 1$）。注意，$y$ 可以与所有 $x_i$ 都不同。

如果有多种还原方式，输出任意一种即可。

说明/提示

在第一个测试用例中，单词可以写成二进制 $x_1 = 10010_2$，$x_2 = 01001_2$ 和 $x_3 = 10101_2$。令 $y = 10001_2$，则 $d(x_1, y) = 2$（第四和第五位不同），$d(x_2, y) = 2$（第一和第二位不同），$d(x_3, y) = 1$（第三位不同）。因此，接近度为 $2 + 2 + 1 = 5$。可以证明无法得到更小的接近度。

在第二个测试用例中，所有形式都等于 $18$（即二进制 $10010_2$），因此最初的形式也是 $18$。很容易看出此时接近度为零。

由 ChatGPT 4.1 翻译

样例

7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42

17
18
1
1
39
0
2