Minecraft
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: bitmasks, brute force, dp, graphs, math

After winning another Bed Wars game, Masha and Olya wanted to relax and decided to play a new game. Masha gives Olya an array $$$a$$$ of length $$$n$$$ and a number $$$s$$$. Now Olya's task is to find a non-negative number $$$x$$$ such that $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = s$$$. But she is very tired after a tight round, so please help her with this.

But this task seemed too simple to them, so they decided to make the numbers larger (up to $$$2^k$$$) and provide you with their binary representation.

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k, n \cdot k \le 2 \cdot 10^6$$$) — the length of the array $$$a$$$ and the length of the binary representation of all numbers.

The second line contains a string of length $$$k$$$, consisting of zeros and ones — the binary representation of the number $$$s$$$, starting from the most significant bits.

The next $$$n$$$ lines also contain strings of length $$$k$$$, consisting of zeros and ones, the $$$i$$$-th of these strings contains the binary representation of the number $$$a_i$$$, starting from the most significant bits.

It is guaranteed that the sum of the values $$$n \cdot k$$$ for all test cases does not exceed $$$2 \cdot 10^6$$$.

Output format:
For each test case, output a string of length $$$k$$$ on a separate line, consisting of zeros or ones — the binary representation of any suitable number $$$x$$$ ($$$x \ge 0$$$), starting from the most significant bits, or $$$-1$$$ if such $$$x$$$ does not exist.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$s = 11, a = [14, 6, 12, 15]$$$, if $$$x = 14$$$, then $$$\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$$$.

In the second test case, $$$s = 41, a = [191, 158]$$$, if $$$x = 154$$$, then $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = (191 \oplus 154) + (158 \oplus 154) = 37 + 4 = 41 = s$$$.

Example input:
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

Example output:
01110
10011010
0010
-1

Editorial:
We will do recursion. Let's go from the lower bits to the significant bits.
$$$rec(i, sum)$$$ means that the first $$$i$$$ bits are selected, the sum of them divided by $$$2^i$$$ equals $$$sum$$$, and the first $$$i$$$ bits match the ones we need. Let $$$cnt_i$$$ — the number of ones in the numbers in the $$$i$$$-th bit. Then we can go from state $$$(i, sum)$$$ to $$$(i + 1, \lfloor \frac{sum + cnt_i}{2} \rfloor)$$$ and $$$(i + 1, \lfloor \frac{sum + n - cnt_i}{2} \rfloor)$$$ if the lowest bit matches the $$$i$$$-th bit in $$$s$$$. There are at most $$$nk$$$ states in such a recursion (proof below). Thus, if we do the memoization, the solution will run $$$O(nk)$$$.
Proof:
$$$sum$$$ is always at most $$$n$$$. At the beginning of the recursion, $$$sum = 0$$$, so the inequality is satisfied. When we go to the next step $$$\frac{sum + cnt_i}{2}$$$, $$$\frac{sum + n - cnt_i}{2} \leq \frac{n + n}{2} = n$$$, which was required to prove.