And and Or - Repovive Premier Round 2 | Repovive

3C. And and Or

1500 pts2s256 MB

You are given an array of integers $a$ of length $n$ .

In one operation, you may choose two indices $i$ and $j$ ( $1 \le i, j \le n$ ) and simultaneously replace:

$a_i \leftarrow a_i \ \&\ a_j$
$a_j \leftarrow a_i \ \vert\ a_j$

Here $\&$ and $\vert$ denote bitwise AND and bitwise OR, respectively (the right-hand sides use the values of $a_i$ and $a_j$ before the operation).

Your task is to obtain the lexicographically smallest array that can be reached after performing any number of operations (possibly zero), and output that array.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \dots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} b_1 \quad b_2 \quad \dots \quad b_n \end{array} \right\} \times t

where $b$ is the lexicographically smallest array achievable from $a$ using the allowed operation.

Samples

Input

Case 1

2
5 2

Case 2

4
7 0 1 6

Case 3

7
3 5 6 1 0 2 7

Explanation

Case 1

Apply the operation on indices 1 and 2, the array becomes: $[0,7]$ .

Case 2

Apply the operation on indices 1 and 2, the array becomes: $[0, 7,1, 6]$ .

Apply the operation on indices 2 and 3, the array becomes: $[0,1,7,6]$ .

Apply the operation on indices 2 and 4, the array becomes: $[0,0,7,7]$ .

Case 3

Apply operations on these pairs (in this order): $(1,5)$ , $(2,6)$ , $(3,4)$ , and $(4,5)$ .

Output

Case 1

0 7

Case 2

0 0 7 7

Case 3

0 0 0 3 7 7 7

You are given an array of integers $a$ of length $n$ .

In one operation, you may choose two indices $i$ and $j$ ( $1 \le i, j \le n$ ) and simultaneously replace:

$a_i \leftarrow a_i \ \&\ a_j$
$a_j \leftarrow a_i \ \vert\ a_j$

Here $\&$ and $\vert$ denote bitwise AND and bitwise OR, respectively (the right-hand sides use the values of $a_i$ and $a_j$ before the operation).

Your task is to obtain the lexicographically smallest array that can be reached after performing any number of operations (possibly zero), and output that array.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \dots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} b_1 \quad b_2 \quad \dots \quad b_n \end{array} \right\} \times t

where $b$ is the lexicographically smallest array achievable from $a$ using the allowed operation.

Apply the operation on indices 1 and 2, the array becomes: $[0,7]$ .

Apply the operation on indices 1 and 2, the array becomes: $[0, 7,1, 6]$ .

Apply the operation on indices 2 and 3, the array becomes: $[0,1,7,6]$ .

Apply the operation on indices 2 and 4, the array becomes: $[0,0,7,7]$ .

Apply operations on these pairs (in this order): $(1,5)$ , $(2,6)$ , $(3,4)$ , and $(4,5)$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3C. And and Or

Input

Output

Samples

3C. And and Or

Constraints

Input

Output

Samples

Constraints