G. Minecraft
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После победы в очередной игре в Bed Wars, Маша и Оля захотели отдохнуть и решили поиграть в новую игру. Маша дает Оле массив $$$a$$$ длины $$$n$$$ и число $$$s$$$. Теперь задача Оли найти такое неотрицательное число $$$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$$$ не существует.

Пример
Входные данные
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$$$, то $$$\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$$$.