Who is the liar?

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

image

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

Please read the guidelines before commenting.


There are no comments at the moment.