在赢得另一场“床战争”游戏后,玛莎和奥莉亚想要放松一下,决定玩一场新游戏。 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$$$。