D. Обратная сумма сортировки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представим, что у вас был массив $$$A$$$ из $$$n$$$ элементов, каждый из которых это $$$0$$$ или $$$1$$$.

Определим функцию $$$f(k,A)$$$, которая возвращает массив $$$B$$$, который является результатом сортировки первых $$$k$$$ элементов массива $$$A$$$ в неубывающем порядке. Например, $$$f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$$$. Обратите внимание, что первые $$$4$$$ элемента были отсортированы.

Рассмотрим массивы $$$B_1, B_2,\ldots, B_n$$$, равные $$$f(1,A), f(2,A),\ldots,f(n,A)$$$. Пусть $$$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$$$. Гарантируется, что такой массив $$$A$$$ существует для данного $$$C$$$.

Входные данные

Первая строка содержит одно целое число $$$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$$$). Если существуют несколько ответов, выведите любой.

Пример
Входные данные
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
Примечание

Рассмотрим первый пример. Начнем с массива $$$A=[1,1,0,1]$$$ и построим массивы $$$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}]$$$
Затем просуммируем каждый столбик и получим $$$C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]$$$.