This is a multi-pass problem. Your solution will be evaluated as an interactive procedure in either of the runs.

In the digital archives of Kivotos, Plana has discovered a collection of mysterious records known as Bitemporal Logs. Each log consists of $n$ entries labeled $1$ to $n$ forming a rooted tree. However, the structural constraints differ depending on whether the temporal flow is retrospective (Logic A) or prospective (Logic B):

• Logic A: The tree is rooted at entry $1$; every other entry $i$ has a parent $p_i$ such that $p_i < i$.
• Logic B: The tree is rooted at entry $n$; every other entry $i$ has a parent $q_i$ such that $q_i > i$.

To analyze the structural properties, Plana defines two types of entries:

• Terminal: An entry that serves as a parent to no other entries.
• Hub: An entry that serves as a parent to at least one other entry.

Plana observed a perfect symmetry called Logical Resonance. This property holds between a Logic A log and a Logic B log if and only if:

For every $i$, entry $i$ is a Terminal in Logic A $\iff$ entry $i$ is a Hub in Logic B.

Plana has mathematically proven that the number of valid Logic A logs and Logic B logs under this constraint is identical. Now, she tasks you with designing a Universal Translation Protocol — a bijection — to transform one log format into the other.

Evaluation of correctness

Your solution is executed twice on each test. In the first run, your solution needs to convert each Logic A log into a Logic B log that satisfies the Logical Resonance condition. In the second run, given a Logic B log produced by your first run, your solution needs to exactly recover the original Logic A log.

The input of the second run consists of the same Logic B logs as your output from the first run, possibly in a different order. For each input Logic B log in the second run, you need to output its corresponding Logic A log. Your solution is considered correct if, for every such Logic B log, your output is exactly the same Logic A log that generated it in the first run.

A testing tool is provided to help you develop and test your solution.

Input

The first line of the input contains two integers $r$ ($r \in \{1, 2\}$) and $T$ ($1 \le T \le 10^5$), representing the run number and the number of test cases.

For each test case, the first line contains an integer $n$ ($2 \le n \le 10^3$).

If $r = 1$, the second line contains $n$ integers $p_1, p_2, \dots, p_n$ representing the Logic A log. It is guaranteed that $p_1 = 0$, and for $2 \le i \le n$, $1 \le p_i < i$ is the entry that entry $i$ is attached to. Here we use $0$ to denote that an entry has no parent (i.e., it is the root).

Otherwise, if $r = 2$, the second line contains $n$ integers $q_1, q_2, \dots, q_n$ representing the Logic B log. It is guaranteed that $q_n = 0$, and for $1 \le i \le n - 1$, $i < q_i \le n$ is the entry that entry $i$ is attached to.

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

Output

If $r = 1$, for each test case, output $n$ integers separated by a space, $q_1, q_2, \dots, q_n$, representing the converted Logic B log. It must hold that $q_n = 0$, and for $1 \le i \le n - 1$, $i < q_i \le n$. The Logical Resonance property must hold: entry $i$ is a Terminal in Logic A if and only if entry $i$ is a Hub in Logic B.

Otherwise, if $r = 2$, for each test case, output $n$ integers separated by a space, $p_1, p_2, \dots, p_n$, representing the restored Logic A log.

Examples

Input 1 (Pass 1)

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

Output 1 (Pass 1)

3 3 4 0
3 4 4 0
2 3 4 0

Input 2 (Pass 2)

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

Output 2 (Pass 2)

0 1 1 1
0 1 1 2
0 1 2 1

Note

Explanation of Sample 1: A possible valid bijection is shown below.

Logic A and Logic B