XOR
XOR
Команда известного криптоаналитика профессора Ксора работает над взломом новой Однородной Приводимой Шифрующей сети. После долгих исследований проблема взлома сети свелась к следующей задаче.
Рассмотрим двоичное представление целых чисел a[1]
, a[2]
, ..., a[n]
, добавив к меньшим из них ведущие нули так чтобы длина (количество цифр) всех чисел стала одинаковой. После этого переставим биты в числах, получив новые числа b[1]
, b[2]
, ..., b[n]
такие что b[1]
xorb[2]
xor ... xorb[n]
= 0. Здесь через xor обозначена операция побитового исключающего или.
Вам, как новичку в команде профессора, следует решить эту задачу.
Входные данные
Первая строка содержит значение n (2 ≤ n ≤ 50). Во второй строке заданы числа a[1]
, a[2]
, ..., a[n]
(1 ≤ a[i]
≤ 10^18
).
Выходные данные
Вывести b[1]
, b[2]
, ..., b[n]
. Если решения не существует, то вывести "impossible".
Замечание
В первом примере a[1]
= 7 = 0111[2]
, a[2]
= 10 = 1010[2]
, a[3]
= 11 = 1011[2]
. Если мы переставим биты и получим b[1]
= 7 = 0111[2]
, b[2]
= 12 = 1100[2]
, b[3]
= 11 = 1011[2]
, то будем иметь b[1]
xorb[2]
xorb[3]
= 0.
Пример
3 7 10 11
14 9 7
3 7 10 3
impossible