火星科学家探索木星众多卫星之一的木卫三。最近,他们发现了一个古代文明的遗址。科学家们将一些用科学未知的语言书写的平板电脑带到了火星。
他们发现木卫三的居民使用由两个字母组成的字母表,每个单词的长度正好是 $$$\ell$$$ 个字母。因此,科学家们决定将这种语言的每个单词写成从 $$$0$$$ 到 $$$2^{\ell} - 1$$$ 的整数。字母表的第一个字母对应于该整数中的零位,第二个字母对应于一位。
同一单词在此语言中可能有多种形式。然后,你需要恢复初始形态。下面描述了这样做的过程。
将两个单词之间的距离表示为这些单词不同的位置数量。例如,$$$1001_2$$$ 和 $$$1100_2$$$(二进制)之间的距离等于 2,因为这些单词从左到右数的第二个和第四个位置具有不同的字母。此外,将单词 $$$x$$$ 和 $$$y$$$ 之间的距离表示为 $$$d(x, y)$$$。
令该单词具有$$$n$$$形式,其中第$$$i$$$用整数$$$x_i$$$描述。所有 $$$x_i$$$ 不一定不同,因为该词的两种不同形式可以写成相同的。考虑一些单词$$$y$$$。那么,单词 $$$y$$$ 的接近度等于到每个单词形式 i 的距离之和。 e.所有 $$$1 \le i \le 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$$$) — 单词形式。整数不一定不同。
输出
对于每个测试,打印一个整数,即单词的初始形式,i。 e.这样 $$$y$$$ ($$$0 \le y \le 2^\ell - 1$$$) 使得所有 $$$1 \le i \le n$$$ 的和 $$$d(x_i, y)$$$ 是最小可能的。请注意,$$$y$$$ 可以与所有整数 $$$x_i$$$ 不同。
如果有多种方法可以恢复初始形式,请打印任意一种。
示例
输入 #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
注意
在第一个测试用例中,这些字可以用二进制写为 $$$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$$$。很容易看出,在这种情况下,紧密度等于零。