假设您有一个由 $$$n$$$ 元素组成的数组 $$$A$$$,每个元素都是 $$$0$$$ 或 $$$1$$$。
让我们定义一个函数$$$f(k,A)$$$,它返回另一个数组$$$B$$$,即按非降序对$$$A$$$ 的前$$$k$$$ 元素进行排序的结果。例如,$$$f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$$$。请注意,前 $$$4$$$ 元素已排序。
现在考虑 $$$f(1,A), f(2,A),\ldots,f(n,A)$$$ 生成的数组 $$$B_1, B_2,\ldots, B_n$$$。令 $$$C$$$ 为通过对 $$$B_1, B_2,\ldots, B_n$$$ 逐元素求和而获得的数组。
例如,令 $$$A=[0,1,0,1]$$$。然后我们有$$$B_1=[0,1,0,1]$$$,$$$B_2=[0,1,0,1]$$$,$$$B_3=[0,0,1,1]$$$,$$$B_4=[0,0,1,1]$$$。那么$$$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]$$$。
您将获得 $$$C$$$。确定一个二进制数组 $$$A$$$,当按上述方式处理时,该数组将给出 $$$C$$$。保证输入中给定的 $$$C$$$ 存在数组 $$$A$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例有两行。第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq n$$$)。保证给定的 $$$C$$$ 存在有效的数组 $$$A$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i$$$ 是 $$$0$$$ 或 $$$1$$$)。如果有多个答案,您可以输出其中任何一个。
示例
输入 #1
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 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1
注意
这是第一个测试用例的解释。鉴于$$$A=[1,1,0,1]$$$,我们可以构造每个$$$B_i$$$:
- $$$B_1=[\color{蓝色}{1},1,0,1]$$$;
- $$$B_2=[\颜色{蓝色}{1},\颜色{蓝色}{1},0,1]$$$;
- $$$B_3=[\颜色{蓝色}{0},\颜色{蓝色}{1},\颜色{蓝色}{1},1]$$$;
- $$$B_4=[\颜色{蓝色}{0},\颜色{蓝色}{1},\颜色{蓝色}{1},\颜色{蓝色}{1}]$$$