← 返回题目列表

Codeforces · 1625/A

A. 古代文明

中文机器翻译题面 查看原题

火星科学家探索木星众多卫星之一的木卫三。最近,他们发现了一个古代文明的遗址。科学家们将一些用科学未知的语言书写的平板电脑带到了火星。

他们发现木卫三的居民使用由两个字母组成的字母表,每个单词的长度正好是 $$$\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$$$。很容易看出,在这种情况下,紧密度等于零。