Ancient Civilization

题意翻译

给定一个长度为 $n$ 的数组 $x_1,x_2,\dots,x_n$，数组中所有的元素的二进制表示不超过 $l$ 位。定义 $d(x,y)$ 为 $x\operatorname{xor} y$ 的二进制表示中 $1$ 的个数，其中 $\operatorname{xor}$ 表示按位异或运算。现在，请求出任意满足要求的整数 $y$，使得 $\sum\limits_{i=1}^n d(x_i,y)$ 最小。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n\leqslant 100$，$1\leqslant l\leqslant 30$。 - $0\leqslant x_i\leqslant 2^l-1$。 Translated by Eason_AC 2022.1.19

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

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

输出样例 #1

17
18
1
1
39
0
2

说明

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.