XOR
XOR
The team of famous cryptoanalyst professor Ksor is working on breaking new Homogenous Reducible Encryption Network. After long investigations the problem of breaking the network was reduced to the following one.
Given several integer numbers a1
, a2
, ..., an
, represent them in binary notation, prepending smaller of them with leading zeroes so that they all had the same number of digits as the largest of them. After that rearrange bits in the numbers to obtain new numbers b1
, b2
, ..., bn
, such that b1
xorb2
xor ... xorbn
= 0. Here xor means bitwise exclusive or.
As a newbie in professor's team, you were assigned to solve the problem.
Input
The first line contains n (2 ≤ n ≤ 50). The second line contains a1
, a2
, ..., an
(1 ≤ ai
≤ 1018
).
Output
Output b1
, b2
, ..., bn
. If there is no solution, output "impossible".
Note
In the first example a1
= 7 = 01112
, a2
= 10 = 10102
, a3
= 11 = 10112
. If we rearrange bits to get b1
= 7 = 01112
, b2
= 12 = 11002
, b3
= 11 = 10112
, we have b1
xorb2
xorb3
= 0.
3 7 10 11
14 9 7
3 7 10 3
impossible