Lexicographically Maximum

Interview

Time limit1sMemory limit1024 MB

Summary

Bits in the same position can be swapped between any two numbers, so find the lexicographically largest array reachable after any number of swaps.

Level: Medium4 of 10
Topics: Bit manipulation, Greedy
Solved: No attempts yet

Problem

A list of $N$ integers $a_1, \dots , a_N$ is stored in the memory of an electronic device. The device has a peculiar operation: bit swapping between numbers. Given integers $i$ , $j$ and $k$ , this operation swaps the $k$ -th bit of $a_i$ with the $k$ -th bit of $a_j$ (and vice versa).

Very interesting phenomena can occur when this operation is performed one or more times, such as obtaining numbers that did not belong to the original list, or numbers larger or smaller than all the original elements.

Use the operation as many times as needed so that the resulting list is lexicographically maximum: $a_1$ is as large as possible, $a_2$ is as large as possible among the lists that maximize $a_1$ , and so on.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ). The second line contains $N$ integers separated by spaces, the list $a_1, \dots , a_N$ ( $0 \le a_i \le 10^9$ ).

Output

Print a single line with $N$ integers separated by spaces, the lexicographically maximum sequence that can be obtained.

Examples2

Example 1
Input
```
4
8 4 2 1
```
Expected output
```
15 0 0 0
```
Example 2
Input
```
4
12 15 1 20
```
Expected output
```
31 13 4 0
```