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 b1xorb2xor ... 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 b1xorb2xorb3 = 0.