Reverse Sort Sum
Description
Suppose you had an array $A$ of $n$ elements, each of which is $0$ or $1$.
Let us define a function $f(k,A)$ which returns another array $B$, the result of sorting the first $k$ elements of $A$ in non-decreasing order. For example, $f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$. Note that the first $4$ elements were sorted.
Now consider the arrays $B_1, B_2,\ldots, B_n$ generated by $f(1,A), f(2,A),\ldots,f(n,A)$. Let $C$ be the array obtained by taking the element-wise sum of $B_1, B_2,\ldots, B_n$.
For example, let $A=[0,1,0,1]$. Then we have $B_1=[0,1,0,1]$, $B_2=[0,1,0,1]$, $B_3=[0,0,1,1]$, $B_4=[0,0,1,1]$. Then $C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]$.
You are given $C$. Determine a binary array $A$ that would give $C$ when processed as above. It is guaranteed that an array $A$ exists for given $C$ in the input.
The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
Each test case has two lines. The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).
The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0 \leq c_i \leq n$). It is guaranteed that a valid array $A$ exists for the given $C$.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
For each test case, output a single line containing $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $0$ or $1$). If there are multiple answers, you may output any of them.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
Each test case has two lines. The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).
The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0 \leq c_i \leq n$). It is guaranteed that a valid array $A$ exists for the given $C$.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output a single line containing $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $0$ or $1$). If there are multiple answers, you may output any of them.
Samples
5
4
2 4 2 4
7
0 3 4 2 3 2 7
3
0 0 0
4
0 0 0 4
3
1 2 3
1 1 0 1
0 1 1 0 0 0 1
0 0 0
0 0 0 1
1 0 1
Note
Here's the explanation for the first test case. Given that $A=[1,1,0,1]$, we can construct each $B_i$:
- $B_1=[\color{blue}{1},1,0,1]$;
- $B_2=[\color{blue}{1},\color{blue}{1},0,1]$;
- $B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]$;
- $B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]$