eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

XOR

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Команда известного криптоаналитика профессора Ксора работает над взломом новой Однородной Приводимой Шифрующей сети. После долгих исследований проблема взлома сети свелась к следующей задаче.

Рассмотрим двоичное представление целых чисел a[1], a[2], ..., a[n], добавив к меньшим из них ведущие нули так чтобы длина (количество цифр) всех чисел стала одинаковой. После этого переставим биты в числах, получив новые числа b[1], b[2], ..., b[n] такие что b[1]xorb[2]xor ... xorb[n] = 0. Здесь через xor обозначена операция побитового исключающего или.

Вам, как новичку в команде профессора, следует решить эту задачу.

Входные данные

Первая строка содержит значение n (2n50). Во второй строке заданы числа a[1], a[2], ..., a[n] (1a[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.

Пример

Входные данные #1
3
7 10 11
Выходные данные #1
14 9 7
Входные данные #2
3
7 10 3
Выходные данные #2
impossible
Автор Андрей Станкевич
Источник 2008 Петрозаводск, Андрей Станкевич Контест 32, Сентябрь 3, Задача К