CF1994G.Minecraft

题意翻译

在赢得一场紧张的 Bed Wars 起床战争游戏后, Masha 和 Olya 想放松一下, Masha 给了 Olya 一个长度为 $n$ 的数组 $a$ 和一个数字 $s$ 。现在请帮助Olya找到一个非负整数 $x$ ，使得 $ \displaystyle\sum_{i=1}^{n} a_i \oplus x = s$ ($ \oplus $表示异或运算)。但是这个任务对他们来说似乎太简单了，所以他们决定把数字变大并以长度为$ k $的二进制形式表示。

每个测试都由多个测试用例组成。第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) 表示测试用例的数量。

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

第二行包含一个长度为 $ k $ 并由 $ 0 $ 和 $ 1 $ 组成的字符串，表示数字 $ s $ 的二进制形式，从最高位开始。

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

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

‭‌‭‏‮⁨⁣⁨⁩‬‍‌⁥‬⁤⁤‍⁦⁦‪⁨‍‮⁥⁩⁨‎​⁦‌⁩‬‭
对于每个测试用例，输出一行长度为 $ k $ 的字符串，该字符串由 $ 0 $ 和 $ 1 $ 组成， 表示任意一个合适的数字 $ x $ ( $ x \ge 0 $ ) 的二进制形式, 从最高位开始。 如果不存在合适的 $ x $ 则输出 $ −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 $ .