During a trip to an island, researcher FireGhost discovered a strange
tribe here. This tribe has ~n~ people, each person in the tribe can be
an *honest* person — always telling the truth, or can be a *liar*
— always lying.

To investigate more about this tribe, FireGhost lined up ~n~ people into a row, then asked each person a question:

- "Is the number of honest people to your left greater than or equal to the one on your right?"

Each person is only allowed to answer "yes" or "no". With their
personality, an *honest* person will always tell the truth; conversely,
a *liar* will always lie.

After that, FireGhost recorded the answers to the questions on a piece
of paper. However, he forgot to record the personality of each person:
who is an *honest* person, and who is a *liar*. Based on the answers to
the questions, please help FireGhost determine the personality of each
person!

#### Input

Each input will consist of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10^4~) — the number of test cases of the problem. The description of the test cases follows.

The first line of each test case contains a positive integer ~n~ (~1 \le n \le 3 \cdot 10^5~) — the number of people in the tribe.

The second line of each test case contains ~n~ integers ~p_1, p_2, \ldots, p_n~ (~p_i \in \left \{ 0, 1 \right \}~) — the answer of each person to the question. If ~p_i = 1~, the answer of person ~i~ is "yes"; conversely, if ~p_i = 0~, the answer of person ~i~ is "no".

The sum of ~n~ over all test cases does not exceed ~3 \cdot 10^5~.

#### Output

Print the answer for each test case:

if it is impossible to determine the personality of each person, print ~-1~.

otherwise, print ~n~ integers ~c_1, c_2, \ldots, c_n~ (~c_i \in \left \{ 0, 1 \right \}~) representing the personality of each person:

if person ~i~ is an

*honest*person (always telling the truth), ~c_i = 1~.conversely, if person ~i~ is a

*liar*(always lying), ~c_i = 0~.

If there are multiple solutions, print any of them.

#### Scoring

Subtask | Score | Constraints |
---|---|---|

~1~ | 500 | ~t \le 100~ and ~n \le 16~ |

~2~ | 1250 | no additional constraints |

Total | 1750 |

#### Sample Input 1

```
3
5
1 0 0 1 0
1
0
3
1 1 1
```

#### Sample Output 1

```
0 1 0 1 0
0
0 0 1
```

#### Notes

Illustration for the first test case.

In the first test case:

The number of

*honest*people to the left and right of person ~1~ are ~0~ and ~2~, respectively. Since person ~1~ is a*liar*, their answer will be "yes".The number of

*honest*people to the left and right of person ~2~ are ~0~ and ~1~, respectively. Since person ~2~ is an*honest*person, their answer will be "no".The number of

*honest*people to the left and right of person ~3~ are ~1~ and ~1~, respectively. Since person ~3~ is a*liar*, their answer will be "no".The number of

*honest*people to the left and right of person ~4~ are ~1~ and ~0~, respectively. Since person ~4~ is an*honest*person, their answer will be "yes".The number of

*honest*people to the left and right of person ~5~ are ~2~ and ~0~, respectively. Since person ~5~ is a*liar*, their answer will be "no".

## Comments