B. Различные элементы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$c$$$. Пусть $$$f(c)$$$ — это количество различных элементов в $$$c$$$. Например, $$$f([1,2,2])=2$$$, потому что в $$$[1,2,2]$$$ два различных элемента: $$$1$$$ и $$$2$$$. Также определим $$$c[i,j]$$$ как подмассив$$$^{\text{∗}}$$$ массива $$$c$$$, ограниченный позициями $$$i$$$ и $$$j$$$ (то есть массив $$$[c_i,c_{i+1},\ldots,c_j]$$$).

Дан массив $$$a$$$ длины $$$n$$$. По нему строится массив $$$b$$$ из $$$n$$$ элементов так, что $$$b_i=f(a[1,i])+f(a[2,i])+\ldots+f(a[i,i])$$$. Вам дан массив $$$b$$$. Найдите любой подходящий массив $$$a$$$ с элементами $$$1 \leq a_i \leq n$$$. Гарантируется, что существует хотя бы один подходящий массив $$$a$$$.

$$$^{\text{∗}}$$$Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) – количество элементов в $$$a$$$ и $$$b$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите любой возможный массив $$$a$$$ на отдельной строке. Массив $$$a$$$ должен удовлетворять условию $$$1\leq a_i\leq n$$$.

Для каждого набора входных данных гарантируется, что существует хотя бы один массив $$$a$$$, который удовлетворяет условиям.

Пример
Входные данные
4
3
1 3 6
3
1 3 5
3
1 3 4
4
1 2 3 7
Выходные данные
1 3 2
2 3 2
3 2 2
4 4 4 1
Примечание

Давайте проверим, что наш вывод для второго набора входных данных корректен:

  • $$$b_1=f([2])=1$$$
  • $$$b_2=f([2,3])+f([3])=2+1=3$$$
  • $$$b_3=f([2,3,2])+f([3,2])+f([2])=2+2+1=5$$$