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.
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]$.
样例
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。