Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
C. Sort?
time limit per test
1 second
memory limit per test
256 megabytes
input
sorting.in
output
standard output

Hamza has created the following sorting algorithm:

To sort an array, he calls sort(1).

He doesn't know how the array ends up after running the algorithm (sorted?), so he's asking for your help.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the length of the array.

The second line contains $$$n$$$ space-separated integers denoting the array $$$a$$$ $$$(0 \leq a_i \leq 10^9)$$$.

Output

Print the final array after running the algorithm on it.

Examples
Input
3
1 2 3
Output
1 3 2
Input
5
3 3 4 2 3
Output
3 3 2 3 4
Note

For simplicity, in this portion of the problem, we'll consider the least significant $$$3$$$ bits.

The $$$and$$$ between two integers $$$x$$$ and $$$y$$$ is the bitwise anding between the two numbers:

$$$1$$$ $$$and$$$ $$$0$$$ $$$=$$$ $$$0$$$ $$$and$$$ $$$1$$$ $$$=$$$ $$$0$$$ $$$and$$$ $$$0$$$ $$$=$$$ $$$0$$$

$$$1$$$ $$$and$$$ $$$1$$$ $$$=$$$ $$$1$$$

For example:

$$$7_{10}$$$ $$$and$$$ $$$5_{10}$$$ $$$=$$$ $$$5_{10}$$$

$$$7_{10}$$$ $$$=$$$ $$${111}_2$$$, $$$5_{10}$$$ $$$=$$$ $$${101}_2$$$

$$${111}_2$$$ $$$and$$$ $$${101}_2$$$ $$$=$$$ $$${101}_2$$$ = $$$5_{10}$$$

The not of an integer $$$x$$$ is taking the complement of the integer (flipping it bits):

$$$not$$$ $$$0$$$ $$$=$$$ $$$1$$$

$$$not$$$ $$$1$$$ $$$=$$$ $$$0$$$

For example:

$$$not$$$ $$$5_{10}$$$ $$$=$$$ $$$2_{10}$$$

Explanation:

$$$5_{10}$$$ $$$=$$$ $$${101}_2$$$

$$$not$$$ $$${101}_2$$$ = $$${010}_2$$$ = $$$2_{10}$$$