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

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

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.

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$.