Statement : D. Permutation Construction

Kirara Magic & PIKASONIC - Flora

You are given an array $a$ consisting of $n$ integers.

For an inversion$^{\text{∗}}$ $(i,j)$ in a permutation$^{\text{†}}$ $p$, its value is defined as $\sum\limits_{k=i}^{j-1} a_k$. The beauty of a permutation is the sum of the values over all its inversions.

You have to construct a permutation $p$ of length $n$ that maximizes its beauty.

$^{\text{∗}}$An inversion in the permutation $p$ of length $n$ is a pair of indices $(i,j)$ such that $1\leq i \lt j\leq n$ and $p_i \gt p_j$. For example, when $p=[1,4,2,3,5]$, the pair $(2,3)$ is an inversion, but $(1,2)$ is not an inversion ($p_1=1$ is not greater than $p_2=4$), and $(4,2)$ is also not an inversion (the index $4$ is not less than $2$). When $p=[1]$, there are no inversions at all.

$^{\text{†}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n \le 2\cdot 10^5$) — the length of $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9\leq a_i\leq 10^9$) — the elements of $a$.

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

For each test case, print a line containing $n$ integers — the permutation $p$ that maximizes its beauty.

If there are multiple valid answers, you may print any of them.

Input

7
1
0
2
1000000000 -1000000000
3
1 2 3
4
-1 -2 -3 -4
5
-1 2 -3 2 -1
6
1 -1 3 -4 1 -3
7
-3 -2 -1 4 -1 -2 -3

Output

1
2 1
3 2 1
1 2 3 4
3 4 1 5 2
5 2 4 1 6 3
1 4 6 7 2 3 5

Note

In the first test case, the permutation $p$ can only be $[1]$.

In the second test case, for the permutation $p=[2,1]$, the only inversion is $(1,2)$, and its value is $10^9$, so the beauty of the permutation is $10^9$. It can be proven that there is no permutation with greater beauty.

In the third test case, for the permutation $p=[3,2,1]$, all inversions are $(1,2)$, $(1,3)$, and $(2,3)$, with values $1$, $3$, and $2$, respectively, so the beauty of the permutation is $1+3+2=6$. It can be proven that there is no permutation with a greater beauty.

In the fourth test case, for the permutation $p=[1,2,3,4]$, there are no inversions, so the beauty of the permutation is $0$. It can be proven that there is no permutation with greater beauty.

In the fifth test case, for the permutation $p=[3,4,1,5,2]$, its beauty is $6$.