CF1625A.Ancient Civilization

Martian scientists explore Ganymede, one of Jupiter's numerous moons. Recently, they have found ruins of an ancient civilization. The scientists brought to Mars some tablets with writings in a language unknown to science.

They found out that the inhabitants of Ganymede used an alphabet consisting of two letters, and each word was exactly $\ell$ letters long. So, the scientists decided to write each word of this language as an integer from $0$ to $2^{\ell} - 1$ inclusively. The first letter of the alphabet corresponds to zero bit in this integer, and the second letter corresponds to one bit.

The same word may have various forms in this language. Then, you need to restore the initial form. The process of doing it is described below.

Denote the distance between two words as the amount of positions, in which these words differ. For example, the distance between $1001_2$ and $1100_2$ (in binary) is equal to two, as these words have different letters in the second and the fourth positions, counting from left to right. Further, denote the distance between words $x$ and $y$ as $d(x, y)$.

Let the word have $n$ forms, the $i$-th of which is described with an integer $x_i$. All the $x_i$ are not necessarily different, as two various forms of the word can be written the same. Consider some word $y$. Then, closeness of the word $y$ is equal to the sum of distances to each of the word forms, i. e. the sum $d(x_i, y)$ over all $1 \le i \le n$.

The initial form is the word $y$ with minimal possible nearness.

You need to help the scientists and write the program which finds the initial form of the word given all its known forms. Note that the initial form is not necessarily equal to any of the $n$ given forms.

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

他们发现，伽尼米德居民使用的字母表仅包含两个字母，且每个单词恰好由 $\ell$ 个字母组成。因此，科学家决定将该语言中的每个单词表示为一个介于 $0$ 到 $2^{\ell} - 1$（含端点）之间的整数：字母表中的第一个字母对应于该整数的二进制表示中的 0 位，第二个字母对应于 1 位。

同一单词在该语言中可能具有多种不同形式。此时，你需要还原出该单词的初始形式。还原过程如下所述。

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

设某单词共有 $n$ 种形式，其中第 $i$ 种形式用整数 $x_i$ 表示。所有 $x_i$ 不一定互不相同，因为该单词的两种不同形式可能被写成相同的整数。考虑某个单词 $y$，则 $y$ 的“亲近度”（closeness）定义为它到所有已知形式的距离之和，即对所有 $1 \le i \le n$ 求和 $d(x_i, y)$。

初始形式即为使亲近度最小的单词 $y$。

你需要帮助科学家编写一个程序，在给定某单词所有已知形式的前提下，找出其初始形式。注意：初始形式不一定等于所给的 $n$ 个形式中的任意一个。

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. The following are descriptions of the test cases.

The first line contains two integers $n$ and $\ell$ ($1 \le n \le 100$, $1 \le \ell \le 30$) — the amount of word forms, and the number of letters in one word.

The second line contains $n$ integers $x_i$ ($0 \le x_i \le 2^\ell - 1$) — word forms. The integers are not necessarily different.

第一行包含一个整数 $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$）—— 单词变体。这些整数不一定互不相同。

For each test, print a single integer, the initial form of the word, i. e. such $y$ ($0 \le y \le 2^\ell - 1$) that the sum $d(x_i, y)$ over all $1 \le i \le n$ is minimal possible. Note that $y$ can differ from all the integers $x_i$.

If there are multiple ways to restore the initial form, print any.

对于每组测试数据，输出一个整数，即该单词的初始形式，也就是满足对所有 $1 \le i \le n$ 的 $d(x_i, y)$ 之和最小的 $y$（其中 $0 \le y \le 2^\ell - 1$）。注意，$y$ 可以与所有整数 $x_i$ 均不相同。

若存在多种方式恢复初始形式，输出任意一种即可。

In the first test case, the words can be written as $x_1 = 10010_2$, $x_2 = 01001_2$ and $x_3 = 10101_2$ in binary. Let $y = 10001_2$. Then, $d(x_1, y) = 2$ (the difference is in the fourth and the fifth positions), $d(x_2, y) = 2$ (the difference is in the first and the second positions), $d(x_3, y) = 1$ (the difference is in the third position). So, the closeness is $2 + 2 + 1 = 5$. It can be shown that you cannot achieve smaller closeness.

In the second test case, all the forms are equal to $18$ ($10010_2$ in binary), so the initial form is also $18$. It's easy to see that closeness is equal to zero in this case.

在第一个测试用例中，这些单词的二进制表示分别为 $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$。显然，此时接近度为 $0$。