D. Permutation Construction
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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).

Input

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$$$.

Output

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.

Example
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$$$.