Problem Background

The glaring sunlight scorches the earth, and as Xiao B walks down the street, a refreshing breeze blows towards him, causing the lush leaves on the roadside to rustle.

"The sound of the summer wind sweeping through the leaves is like rain."

Problem Description

Alice and Bob are planting trees and decide to play a game.

Alice owns nodes $1\sim n$, and Bob owns nodes $(n+1)\sim 2n$. These $2n$ nodes have weights that form a permutation $a$, where $a_i$ is the weight on node $i$.

First, they agree that node $1$ is the root of the tree.

Then, Alice decides the parent for nodes $2\sim n$, where the parent of node $i$ can only be chosen from nodes $1\sim(i-1)$.

Next, Bob decides the parent for nodes $(n+1)\sim 2n$, where the parent of node $i$ can be chosen from nodes $0\sim(i-1)$. Node $0$ is not part of their tree, meaning Bob's nodes do not necessarily need to be connected to this tree.

Finally, Alice will start a depth-first search (DFS) from node $1$ and maintain a sequence. During the search, every time she encounters an unvisited node, she adds its weight to the end of the sequence.

Alice wants the final sequence to have the smallest possible lexicographical order, while Bob wants the largest possible lexicographical order, and both will use optimal strategies. Now, Bob asks you to tell him what the final sequence will be.

Here is the definition of lexicographical order:

• For a sequence $a$ of length $n$, if $i > n$, we define $a_i = -\infty$.
• For two sequences $a$ and $b$, we define that $a$ has a smaller lexicographical order than $b$ if and only if there exists $i \geq 1$ such that $\forall 1 \leq j < i$, $a_j = b_j$ and $a_i < b_i$.

Input Format

In some test cases, Bob will tell you the parents of nodes $2\sim n$ that Alice has decided in the first step.

The first line contains an integer $t$, indicating the subtask number. Specifically, the subtask number for the example is $0$.

The second line contains a positive integer $n$.

The third line contains $2n$ positive integers, representing the permutation $a$.

The fourth line contains $(n-1)$ integers. If the subtask has special property A, these integers represent the parents of nodes $2\sim n$; otherwise, these $(n-1)$ integers are all $0$.

Output Format

One line containing the final sequence.

Sample Input and Output

Input Sample #1

0
5
10 5 1 8 4 3 7 6 2 9
1 1 1 3

Output Sample #1

10 1 4 9 7 6 5 8 3 2

Input Sample #2

0
4
7 2 4 1 5 6 3 8
0 0 0

Output Sample #2

7 1 8 2 4 6 5 3

Input Sample #3

0
4
2 7 6 4 5 8 1 3
0 0 0

Output Sample #3

2 4 8 6 7 5 3

Notes

In Sample #1, one possible final tree, with numbers representing node IDs and weights in parentheses:

Data Range

Special Property A: The input specifies the parents of nodes $2\sim n$ in one of Alice's optimal decisions.

Special Property B: $a_{n+1}\sim a_{2n}$ forms a permutation of $1\sim n$.

For $100\%$ of the data, $1 \le n \le 10^5$, and the sequence $a$ is guaranteed to be a permutation of $1\sim 2n$.

见题面 Input 部分

见题面 Output 部分