Goodman

Time limit: 0.7s Memory limit: 256MB Input: Output:

S'all good, man.

  • James McGill, Better Call Saul

Saul Goodman is the best lawyer in the world. He believes that until proven guilty, every man, woman, and child in this country is innocent. However, one client of Saul is not so innocent.

Saul needs to build a solid story for his defense. There were nn events, numbered from 11 to nn. Saul needs to come up with an order q1,q2,…,qnq_1, q_2, \ldots, q_n, in which these events happened. His client, however, has a poor memory! If Saul tells him to remember permutation (q1,q2,…,qn)(q_1, q_2, \ldots, q_n) of events, he will remember permutation (pq1,pq2,…,pqn)(p_{q_1}, p_{q_2}, \ldots, p_{q_n}), where (p1,p2,…,pn)(p_1, p_2, \ldots, p_n) is some (fixed) permutation of integers from 11 to nn.

Saul wants their permutations to be as consistent as possible: he wants to maximize the value of LCS((q1,q2,…,qn),(pq1,pq2,…,pqn))LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n})). Help him to find permutation (q1,q2,…,qn)(q_1, q_2, \ldots, q_n) which maximizes this value! If there are many such permutations, find any of them.

Here LCS(a,b)LCS(a, b) denotes the length of the longest common subsequence of sequences aa and bb. For example, LCS((1,3,4,2,5),(3,1,2,4,5))=3LCS((1, 3, 4, 2, 5), (3, 1, 2, 4, 5)) = 3, and one of the common subsequences of length 33 is (1,2,5)(1, 2, 5).

Input data

The first line contains a single integer tt (1≀t≀1051 \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 nn (1≀n≀1061 \leq n \leq 10^6) - the length of the permutation.

The second line of each test case contains nn integers p1,p2,…,pnp_1, p_2, \ldots, p_n (1≀pi≀n1 \le p_i \le n, all pip_i are distinct) - the elements of the permutation.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

Output data

For each test case, output nn integers q1,q2,…,qnq_1, q_2, \ldots, q_n (1≀qi≀n1 \le q_i \le n, all qiq_i are distinct) ~--- any permutation of integers from 11 to nn, which maximizes the value of LCS((q1,q2,…,qn),(pq1,pq2,…,pqn))LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n})).

Example

stdin

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

stdout

1 2 3 4 
1 6 2 5 3 4 

Explanation

In the first test case, for q=(1,2,3,4)q = (1, 2, 3, 4), we have LCS((1,2,3,4),(p1,p2,p3,p4))LCS((1, 2, 3, 4), (p_1, p_2, p_3, p_4)) = LCS((1,2,3,4),(1,2,3,4))=4LCS((1, 2, 3, 4), (1, 2, 3, 4)) = 4.

In the second test case, for q=(1,6,2,5,3,4)q = (1, 6, 2, 5, 3, 4), we have:

LCS((1,6,2,5,3,4),(p1,p6,p2,p5,p3,p4))LCS((1, 6, 2, 5, 3, 4), (p_1, p_6, p_2, p_5, p_3, p_4)) = LCS((1,6,2,5,3,4),(6,1,5,2,4,3))LCS((1, 6, 2, 5, 3, 4), (6, 1, 5, 2, 4, 3)) = 3KaTeX parse error: Can't use function '$' in math mode at position 40: …nces of length $Μ²3 is (1,2,3)(1, 2, 3).

Log in or sign up to be able to send submissions!