我的世界

时间限制：2 秒
空间限制：512 MB

又赢了一局起床战争后，Masha 和 Olya 想放松一下，决定玩一个新游戏。Masha 给 Olya 一个长度为 $n$ 的数组 $a$ 和一个数 $s$。Olya 的任务是找到一个非负整数 $x$，使得 $\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$ 的字符串，由 0 和 1 组成 —— 数字 $s$ 的二进制表示，从最高位开始。

接下来的 $n$ 行也包含长度为 $k$ 的字符串，由 0 和 1 组成，第 $i$ 行包含数字 $a_i$ 的二进制表示，从最高位开始。

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

输出格式

对于每个测试用例，在单独的一行中输出一个长度为 $k$ 的字符串，由 0 或 1 组成 —— 任意一个满足条件的数字 $x$（$x \ge 0$）的二进制表示，从最高位开始；如果这样的 $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

样例输出

01110
10011010
0010
-1

样例解释

在第一个测试用例中，$s = 11$，$a = [14, 6, 12, 15]$。若取 $x = 14$，则 $\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$，则 $\sum (a_i \oplus x) = (191 \oplus 154) + (158 \oplus 154) = 37 + 4 = 41 = s$