Problem Description

You are given $ N $ non-negative integers $A_1, A_2, \cdots, A_N$. For each $k = 1, 2, \cdots, N$, solve the following problem:

Alice and Bob play a game as follows:

• Alice selects $ k $ numbers from $A_1, A_2, \cdots, A_N$. Let the selected numbers be $x_1, x_2, \cdots, x_k$ (unordered).

• Bob constructs a non-negative integer sequence $y = (y_1, y_2, \cdots, y_{2k})$ with the following conditions:

• $0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}$

• Define $z_i = y_{2i-1} \oplus y_{2i}$. Then, the multiset $\{z_1, z_2, \cdots, z_k\}$ must match the multiset $\{x_1, x_2, \cdots, x_k\}$.

Here, $\oplus$ denotes the bitwise XOR operation.

The score of the game is defined as the value of $ y_{2k} $. Bob aims to minimize the score, while Alice aims to maximize it. What will be the score under the optimal actions of both players?

The bitwise XOR operation for non-negative integers $ A $ and $ B $, denoted $A \oplus B$, is defined as follows:

• When $A \oplus B$ is written in binary, the digit in the $ 2^k $ place ($k \geq 0$) is $ 1 $ if exactly one of the corresponding digits of $ A $ and $ B $ in the $ 2^k $ place is $ 1 $, otherwise it is $ 0 $.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

Generally, the bitwise XOR of $ k $ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proven that this value is independent of the order of $p_1, p_2, p_3, \dots, p_k$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

2
6
6

Sample Input #2

5
1 1 1 1 1

Sample Output #2

1
3
5
7
9

Sample Input #3

5
1 2 4 8 16

Sample Output #3

16
24
28
30
31

Sample Input #4

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

Sample Output #4

536870912
1610612736
2684354560
3758096384
4831838208
4831838208
4831838208
4831838208
4831838208
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664
5100273664

Notes/Hints

Constraints

• $1 \leq N \leq 250000$
• $1 \leq A_i \leq 10^9$
• All values in the input are integers.

Sample Explanation 1

Consider the case $ k = 1 $:
- If Alice selects $ x_1 = 1 $: Bob can construct $ y = (0, 1) $, resulting in a score of $ 1 $.
- If Alice selects $ x_1 = 2 $: Bob can construct $ y = (0, 2) $, resulting in a score of $ 2 $.
- If Alice selects $ x_1 = 3 $: Bob can construct $ y = (1, 2) $, resulting in a score of $ 2 $.
Thus, Alice will select $ x_1 = 2 $ or $ x_1 = 3 $, and the score will be $ 2 $.

Consider the case $ k = 2 $:
Alice selects $ (x_1, x_2) = (2, 3) $, and Bob constructs $ y = (1, 2, 4, 6) $, resulting in a score of $ 6 $. This is an example of the optimal actions of both players, and the answer is $ 6 $.

Consider the case $ k = 3 $:
Alice selects $ (x_1, x_2, x_3) = (1, 2, 3) $, and Bob constructs $ y = (0, 1, 1, 2, 4, 6) $, resulting in a score of $ 6 $. This is an example of the optimal actions of both players, and the answer is $ 6 $.

见题面 Input 部分

见题面 Output 部分