Haha, try to solve this, SelectorUnlimited!
— antontrygubO_o
Ваши друзья Алиса и Боб практикуют гадания.
Гадание производится следующим образом: есть хорошо всем известный массив \(a\) из \(n\) неотрицательных целых чисел, пронумерованных от \(1\) до \(n\). Клиент выбирает некоторое неотрицательное число \(d\), а затем последовательно применяет одну из двух операций для каждого \(i = 1, 2, \ldots, n\), в возрастающем порядке \(i\). Возможные операции таковы:
- текущее число \(d\) заменяется на \(d + a_i\)
- текущее число \(d\) заменяется на \(d \oplus a_i\) (здесь и далее \(\oplus\) обозначает побитовое исключающее или)
Обратите внимание, что выбранная операция может быть разной для разных \(i\) и разных клиентов.
Однажды Алиса выбрала \(d = x\), а Боб выбрал \(d = x + 3\). Каждый из них сходил к гадалке и в конце концов получил какое-то число. Заметьте, что Алиса и Боб выбирают операции независимо, иначе говоря, для каких-то \(i\) они могли выбирать как одну операцию, так и разные.
Вы каким-то образом узнали, что то ли Алиса, то ли Боб в итоге получили число \(y\), но кто именно — неизвестно. Ваша задача — зная числа, с которых начали Алиса и Боб, узнать, кто же из них получил в итоге число \(y\). Гарантируется, что на тестах жюри ровно один из ваших друзей мог получить \(y\).
Взломы
Вы не можете делать взломы по этой задаче.
Примечание
В первом наборе входных данных Алиса могла получить \(9\) с помощью следующих операций: \(7 + 2 = 9\).
Во втором наборе Алиса могла получить \(2\) с помощью таких операций: \((0 + 1) \oplus 3 = 2\).
В третьем наборе Боб изначально имел число \(x+3 = 0+3=3\). Тогда он мог получить \(1\) таким образом: \((((3 + 1) + 2) \oplus 3) \oplus 4 = 1\).