После победы в очередной игре в 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$$$ не существует.
44 501011011100011001100011112 80010100110111111100111105 40101001000000000001000116 500011101101100101010111001001110000
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$$$.
Название |
---|