После победы в очередной игре в Bed Wars, Маша и Оля захотели отдохнуть и решили поиграть в новую игру. Маша дает Оле массив \(a\) длины \(n\) и число \(s\). Теперь задача Оли найти такое неотрицательное число \(x\), что \(\displaystyle\sum_{i=1}^{n} a_i \oplus x = s\). Но она очень устала после напряженного раунда, поэтому, пожалуйста, помогите ей в этом.
Но такая задача показалась им слишком простой, поэтому они решили сделать числа большими (до \(2^k\)) и предоставить вам их двоичное представление.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите строку длины \(k\), состоящую из нулей или единиц — битовую запись любого подходящего числа \(x\) (\(x \ge 0\)), начиная со старших битов, или \(-1\), если такого \(x\) не существует.
Примечание
В первом наборе входных данных \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|