E. Chorki
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$n$$$ consisting only of numbers $$$0$$$ and $$$1$$$. You may obtain another array $$$A'$$$ by performing a cyclic rotation of $$$A$$$ by any number of positions (possibly zero).

A cyclic rotation shifts elements of an array circularly. For example, rotating $$$[1, 0, 1, 1, 0]$$$ gives: $$$$$$ [1, 0, 1, 1, 0], \; [0, 1, 1, 0, 1], \; [1, 1, 0, 1, 0], \; [1, 0, 1, 0, 1], \; [0, 1, 0, 1, 1] $$$$$$

Define an array $$$B$$$ as follows: $$$$$$B[i] = A[i] \oplus A'[i] \quad \text{for all } 0 \le i \lt n$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.

An array $$$X$$$ is said to be lexicographically larger than an array $$$Y$$$ if:

  • at the first position where they differ, $$$X$$$ has a $$$1$$$ and $$$Y$$$ has a $$$0$$$.

Your task is to determine the lexicographically maximum binary array $$$B$$$ that can be obtained among all possible cyclic rotations of $$$A$$$.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

Each test case consists of two lines:

  • The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the array $$$A$$$.
  • The second line contains $$$n$$$ integers $$$A_1, A_2, \dots, A_n$$$ $$$(A_i \in \{0, 1\})$$$ — the elements of the array $$$A$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers separated by spaces — the lexicographically maximum binary array $$$B$$$.

Example
Input
2
4
1 1 0 0
5
1 0 1 1 0
Output
1 1 1 1 
1 1 1 0 1
Note

Consider the first test case where $$$A = [1, 1, 0, 0]$$$. The array has 4 cyclic rotations: $$$$$$ [1, 1, 0, 0], \; [1, 0, 0, 1], \; [0, 0, 1, 1], \; [0, 1, 1, 0]. $$$$$$

Calculating $$$B$$$ for each rotation:

  • If $$$A' = [1, 1, 0, 0]$$$, then $$$B = [0, 0, 0, 0]$$$.
  • If $$$A' = [1, 0, 0, 1]$$$, then $$$B = [0, 1, 0, 1]$$$.
  • If $$$A' = [0, 0, 1, 1]$$$, then $$$B = [1, 1, 1, 1]$$$.
  • If $$$A' = [0, 1, 1, 0]$$$, then $$$B = [1, 0, 1, 0]$$$.

Among all possible rotations $$$A'$$$, the lexicographically maximum $$$B$$$ is $$$[1, 1, 1, 1]$$$.