АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1332. Cryptography

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

One of the simplest encryption methods is to apply the bitwise exclusive or (xor) operator to the input message using an encryption key. However, this method is secure only when the input message is no longer that the encryption key, otherwise even a small portion of additional information about the original message might lead to a successful attack.

Suppose you are given an original message that is split into k 32-bit blocks. The blocks are encrypted independently by applying xor operator against the encryption key Key, which is also 32 bits long. Each input block is a non-negative integer. It is known that the input blocks form a nondecreasing sequence
a1, a2, a2, …, ak.

You will be presented the encrypted sequence b1, b2, b3, …, bk (bi = ai xor Key). Your task is to unambiguously recover the encryption key Key, or report that it is impossible to do so.

Limitations

32 <= k <= 100 000.

0 <= ai, bi <= 232 – 1.

You can safely assume that the sequence b1, b2, b3, …bk is produced by applying xor operator to a nondecreasing sequence a1, a2, a3, …ak using some Key.

Input

The first line of the input file contains an integer k. The second line contains k space-delimited integers b1, b2, b3, … bk.

Output

The output file should contain the encryption key Key if it is possible to unambiguously recover it, or the word “Impossible” (without quotation marks) otherwise.

Example

Input

Output

32

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Impossible

33

7 6 5 3 15 23 39 71 135 263 519 1031 2055 4103 8199 16391 32775 65543 131079 262151 524295 1048583 2097159 4194311 8388615 16777223 33554439 67108871 134217735 268435463 536870919 1073741831 2147483655

7

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1331. G - Bus Conductor 1332. 1333. I - Belt Drive 1334. J - Dominoes 1335. K - Embroidery
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.