B. Бесси и MEX
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
MOOO! - Doja Cat
⠀

У фермера Джона есть перестановка $$$p_1, p_2, \ldots, p_n$$$, в которой каждое целое число от $$$0$$$ до $$$n-1$$$ встречается ровно один раз. Он дает Бесси массив $$$a$$$ длины $$$n$$$ и просит ее восстановить $$$p$$$ на основе $$$a$$$.

Массив $$$a$$$ строится так: $$$a_i$$$ = $$$\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$$$, где $$$\texttt{MEX}$$$ массива — это минимальное целое неотрицательное число, которое не встречается в этом массиве. Например, $$$\texttt{MEX}(1, 2, 3) = 0$$$, а $$$\texttt{MEX}(3, 1, 0) = 2$$$.

Помогите Бесси построить любую перестановку $$$p$$$, удовлетворяющую массиву $$$a$$$. Гарантируется, что вам даются входные данные, для которых существует хотя бы одна допустимая перестановка $$$p$$$. Если существует несколько возможных $$$p$$$, вы можете вывести любую из них.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длину $$$p$$$ и $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-n \leq a_i \leq n$$$) — элементы массива $$$a$$$.

Гарантируется, что существует хотя бы одна подходящая перестановка $$$p$$$ для каждого данного набора данных.

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

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

Для каждого набора входных данных выведите на отдельной строке $$$n$$$ целых чисел, являющихся элементами $$$p$$$.

Если существует несколько решений, выведите любое из них.

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

В первом наборе входных данных $$$p = [0, 1, 4, 2, 3]$$$ является одним из возможных ответов.

Для этой перестановки $$$a$$$ будет вычисляться так: $$$a_1 = \texttt{MEX}(0) - 0 = 1$$$, $$$a_2 = \texttt{MEX}(0, 1) - 1 = 1$$$, $$$a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2$$$, $$$a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1$$$, $$$a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2$$$.

Таким образом, как и требовалось, $$$a$$$ будет равняться $$$[1, 1, -2, 1, 2]$$$.