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