K. Are you a bot?
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

"What does the heartbeat of a bot, arranged into a graph, look like?"

You have a competitive programming bot, whose heart beats $$$n$$$ times per minute. The intensity of the $$$i$$$-th heartbeat is $$$a_i$$$. Here, $$$a_1\sim a_n$$$ is a permutation of $$$1\sim n$$$.

Let $$$A_i$$$ be the sequence obtained by deleting the $$$i$$$-th element from the sequence $$$a$$$, i.e., $$$A_i=[a_1,\cdots,a_{i-1},a_{i+1},\cdots,a_n]$$$.

For a sequence $$$p$$$ of distinct elements, let $$$G(p)$$$ be an undirected graph with $$$|p|$$$ vertices, numbered $$$1\sim |p|$$$. For every pair of positive integers $$$1\le i \lt j\le |p|$$$, if $$$\forall k\in [i,j]\cap \mathbb{Z}$$$, we have $$$p_k\in [\min(p_i,p_j),\max(p_i,p_j)]$$$, then in $$$G(p)$$$, there is an edge between vertices $$$i$$$ and $$$j$$$. Let $$$F(p)$$$ be the shortest path length from vertex $$$1$$$ to vertex $$$|p|$$$ in $$$G(p)$$$, where a path length is defined as its number of edges.

Let $$$f(a)=[F(A_1),F(A_2),\dots,F(A_n)]$$$.

Given a sequence of length $$$n$$$ as $$$[b_1,\cdots,b_n]$$$, your task is to find any permutation $$$a$$$ of $$$1\sim n$$$ such that $$$f(a)=b$$$.

It is guaranteed that at least one solution exists.

Input

There are multiple test cases in a single test file.

The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 40\,000$$$), indicating the number of the test cases.

For each of the test case:

  • The first line contains a single integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$).
  • The next line contains $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$.
  • It is guaranteed that at least one solution exists.

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

Output

For each test case, output a single line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$, indicating the permutation you found.

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

Example
Input
11
4
2 2 1 1
4
2 2 2 2
4
2 1 1 2
7
5 5 4 4 4 5 5
7
1 3 2 2 2 2 4
7
3 3 2 4 4 5 3
8
2 2 3 5 3 3 3 4
8
5 4 4 4 4 6 6 5
8
4 4 4 2 4 4 2 3
9
4 7 5 5 5 5 3 4 4
9
3 4 4 4 4 4 4 4 6
Output
1 2 4 3 
2 1 4 3 
1 3 2 4 
3 1 7 2 6 4 5 
3 1 6 4 2 5 7 
2 3 1 6 4 7 5 
5 6 3 1 7 4 2 8 
1 8 2 7 3 5 6 4 
6 3 2 7 4 5 1 8 
5 8 6 3 7 1 9 2 4 
8 1 7 9 2 5 3 4 6