I. Increasing Income
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Everything i did, I did it for me.
—Walter White, Breaking Bad

Walter always says he is doing everything for his family. But in reality, due to his ego, he became obsessed with making as much money as possible.

It turned out that his income would be equal to the maximal possible value of $$$f((q_1, q_2, \ldots, q_n)) + f((p_{q_1}, p_{q_2}, \ldots, p_{q_n}))$$$ over all permutations $$$(q_1, q_2, \ldots, q_n)$$$ of integers from $$$1$$$ to $$$n$$$.

Here $$$p_1, p_2, \ldots, p_n$$$ is Walt's favorite permutation, and $$$f(a)$$$ is defined as the number of positions $$$1 \le i \le n$$$, for which $$$a_i = \max(a_1, a_2, \ldots, a_i)$$$: in other words, the number of prefix maximums.

Find any permutation $$$(q_1, q_2, \ldots, q_n)$$$ of integers from $$$1$$$ to $$$n$$$ that maximizes Walt's income. If there are many such permutations, find any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$)  — the length of Walt's favorite permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — elements of the permutation.

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 $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$, all $$$q_i$$$ are distinct)  — any permutation of integers from $$$1$$$ to $$$n$$$, which maximizes the value of $$$f((q_1, q_2, \ldots, q_n)) + f((p_{q_1}, p_{q_2}, \ldots, p_{q_n}))$$$

Example
Input
3
3
1 2 3
4
2 4 3 1
5
1 5 2 4 3
Output
1 2 3 
1 3 4 2 
1 3 5 4 2
Note

In the first test case, for $$$q = (1, 2, 3)$$$, the value is $$$f(1, 2, 3) + f(p_1, p_2, p_3) = f(1, 2, 3) + f(1, 2, 3) = 3 + 3 = 6$$$.

In the second test case, for $$$q = (1, 3, 4, 2)$$$, the value is $$$f(1, 3, 4, 2) + f(p_1, p_3, p_4, p_2) = f(1, 3, 4, 2) + f(2, 3, 1, 4) = 3 + 3 = 6$$$.

In the third test case, for $$$q = (1, 3, 5, 4, 2)$$$, the value is $$$f(1, 3, 5, 4, 2) + f(p_1, p_3, p_5, p_4, p_2) = f(1, 3, 5, 4, 2) + f(1, 2, 3, 4, 5) = 3 + 5 = 8$$$.