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, Задача К