← 返回题目列表

Codeforces · 1994/G

G. 我的世界

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

在赢得另一场“床战争”游戏后,玛莎和奥莉亚想要放松一下,决定玩一场新游戏。 Masha 给 Olya 一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个数字 $$$s$$$。现在 Olya 的任务是找到一个非负数 $$$x$$$ 使得 $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = s$$$。但在紧张的一轮比赛后她很累,所以请帮助她。

但这个任务对他们来说似乎太简单了,因此他们决定将数字变大(最多 $$$2^k$$$)并为您提供他们的二进制表示形式。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k, n \cdot k \le 2 \cdot 10^6$$$) - 数组 $$$a$$$ 的长度和所有数字的二进制表示的长度。

第二行包含一个长度为 $$$k$$$ 的字符串,由零和一组成 - 数字 $$$s$$$ 的二进制表示形式,从最高有效位开始。

接下来的 $$$n$$$ 行还包含长度为 $$$k$$$ 的字符串,由零和一组成,这些字符串的第 $$$i$$$ 包含数字 $$$a_i$$$ 的二进制表示形式,从最高有效位开始。

保证所有测试用例的值 $$$n \cdot k$$$ 之和不超过 $$$2 \cdot 10^6$$$。

输出

对于每个测试用例,在单独的行上输出长度为 $$$k$$$ 的字符串,由零或一组成 - 任何合适数字 $$$x$$$ ($$$x \ge 0$$$) 的二进制表示形式,从最高有效位开始,或 $$$-1$$$(如果 $$$x$$$ 不存在)。

示例

输入 #1

4
4 5
01011
01110
00110
01100
01111
2 8
00101001
10111111
10011110
5 4
0101
0010
0000
0000
0010
0011
6 5
00011
10110
11001
01010
11100
10011
10000

输出 #1

01110
10011010
0010
-1

注意

在第一个测试用例中,$$$s = 11, a = [14, 6, 12, 15]$$$,如果 $$$x = 14$$$,则 $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = (14 \oplus 14) + (6 \oplus 14) + (12 \oplus 14) + (15 \oplus 14) = 0 + 8 + 2 + 1 = 11 = s$$$。

在第二个测试用例中,$$$s = 41, a = [191, 158]$$$,如果 $$$x = 154$$$,则 $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = (191 \oplus 154) + (158 \oplus 154) = 37 + 4 = 41 = s$$$。