311153: CF1942B. Bessie and MEX

B. Bessie and MEXtime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMOOO! - Doja Cat⠀

Farmer John has a permutation $p_1, p_2, \ldots, p_n$, where every integer from $0$ to $n-1$ occurs exactly once. He gives Bessie an array $a$ of length $n$ and challenges her to construct $p$ based on $a$.

The array $a$ is constructed so that $a_i$ = $\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$, where the $\texttt{MEX}$ of an array is the minimum non-negative integer that does not appear in that array. For example, $\texttt{MEX}(1, 2, 3) = 0$ and $\texttt{MEX}(3, 1, 0) = 2$.

Help Bessie construct any valid permutation $p$ that satisfies $a$. The input is given in such a way that at least one valid $p$ exists. If there are multiple possible $p$, it is enough to print one of them.

Input

The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the lengths of $p$ and $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-n \leq a_i \leq n$) — the elements of array $a$.

It is guaranteed that there is at least one valid $p$ for the given data.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ integers on a new line, the elements of $p$.

If there are multiple solutions, print any of them.

ExampleInput

3
5
1 1 -2 1 2
5
1 1 1 1 1
3
-2 1 2

Output

0 1 4 2 3 
0 1 2 3 4 
2 0 1 

Note

In the first case, $p = [0, 1, 4, 2, 3]$ is one possible output.

$a$ will then be calculated as $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$.

So, as required, $a$ will be $[1, 1, -2, 1, 2]$.

题目大意：
Bessie和MEX

农夫约翰有一个长度为n的排列p_1, p_2, ..., p_n，其中每个整数从0到n-1恰好出现一次。他给Bessie一个长度为n的数组a，并挑战她基于a来构建p。

数组a是根据a_i = MEX(p_1, p_2, ..., p_i) - p_i构建的，其中MEX数组是最小的非负整数，该整数不出现在该数组中。例如，MEX(1, 2, 3) = 0和MEX(3, 1, 0) = 2。

帮助Bessie构建一个有效的排列p，满足a。输入方式保证至少存在一个有效的p。如果有多个可能的p，打印其中一个即可。

输入数据格式：
第一行包含t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——p和a的长度。
每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（-n≤a_i≤n）——数组a的元素。
保证对于给定的数据至少存在一个有效的p。
保证所有测试用例的n之和不超过2×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] 是一个可能的输出。根据p计算出的a将是[1, 1, -2, 1, 2]。题目大意： Bessie和MEX 农夫约翰有一个长度为n的排列p_1, p_2, ..., p_n，其中每个整数从0到n-1恰好出现一次。他给Bessie一个长度为n的数组a，并挑战她基于a来构建p。 数组a是根据a_i = MEX(p_1, p_2, ..., p_i) - p_i构建的，其中MEX数组是最小的非负整数，该整数不出现在该数组中。例如，MEX(1, 2, 3) = 0和MEX(3, 1, 0) = 2。 帮助Bessie构建一个有效的排列p，满足a。输入方式保证至少存在一个有效的p。如果有多个可能的p，打印其中一个即可。 输入数据格式： 第一行包含t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——p和a的长度。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（-n≤a_i≤n）——数组a的元素。 保证对于给定的数据至少存在一个有效的p。 保证所有测试用例的n之和不超过2×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] 是一个可能的输出。根据p计算出的a将是[1, 1, -2, 1, 2]。