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 a[1], a[2], ..., a[n], 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 b[1], b[2], ..., b[n], such that b[1] xor b[2] xor ... xor b[n] = 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 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^18).

Output

Output b[1], b[2], ..., b[n]. If there is no solution, output "impossible".

Examples

Note

In the first example a[1] = 7 = 0111[2], a[2] = 10 = 1010[2], a[3] = 11 = 1011[2]. If we rearrange bits to get b[1] = 7 = 0111[2], b[2] = 12 = 1100[2], b[3] = 11 = 1011[2], we have b[1] xor b[2] xor b[3] = 0.