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
|
