A. Mr. Wow and Lucky Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An array $$$c$$$ of size $$$n$$$ is called Lucky array if it satisfies the following conditions for every $$$i(1 \le i \le n)$$$:

  1. $$$c_i$$$ is either $$$0$$$ or $$$1$$$;
  2. $$$c_1 + c_2 + \ldots + c_i \le ⌊\frac{i}{2}⌋ $$$.

Mr. Wow has constructed a Lucky array $$$a$$$ of size $$$n$$$. Now he wants you to construct a Lucky array $$$b$$$ of size $$$n$$$ such that :

  1. $$$b ≠ a$$$. In other words, there is at least one index $$$i(1 \le i \le n)$$$ satisfying $$$a_i \neq b_i$$$;
  2. The value of $$$(b_1 + b_2 + \ldots + b_{n-1} + b_{n})$$$ is maximum possible.

If there is no Lucky array satisfying Mr. Wow's conditions, print $$$-1$$$ instead.

Note that, $$$⌊y⌋$$$ means the largest integer which is not greater than $$$y$$$, i.e., $$$⌊2.75⌋ = 2, ⌊3.99⌋ = 3, ⌊4⌋ = 4$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the Lucky array $$$a$$$.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$0 \le a_{i} \le 1$$$).

It is guaranteed that the given array $$$a$$$ is a Lucky array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print $$$-1$$$ if there is no Lucky array satisfying Mr. Wow's conditions.

Otherwise, print $$$n$$$ space-separated integers $$$b_i$$$ ($$$0 \le b_{i} \le 1$$$) which satisfy the conditions by Mr. Wow.

Example
Input
5
1
0
2
0 1
4
0 0 1 0
5
0 1 0 0 1
6
0 0 0 0 0 0
Output
-1
0 0
0 1 0 1
0 0 1 1 0
0 0 1 1 0 1