题目背景

刺眼的阳光把大地烤得炽热，小 B 走在街上，迎面吹来一阵清风，路旁郁郁葱葱的树叶沙沙地摇晃着。

“夏风扫过树叶的声音就像下雨一样呢。”

题目描述

Alice 和 Bob 在种树，同时，他们决定玩一个游戏。

Alice 拥有 $1\sim n$ 号结点，Bob 拥有 $(n+1)\sim 2n$ 号结点，这 $2n$ 个结点的权值恰好构成一个排列 $a$，其中 $a_i$ 为 $i$ 号点上的权值。

首先，他们约定 $1$ 号点为树根。

然后，由 Alice 为 $2\sim n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $1\sim(i-1)$ 中选择。

接下来，由 Bob 为 $(n+1)\sim 2n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $0\sim(i-1)$ 中选择。$0$ 号点不在他们的树上，也就是说，Bob 的结点不一定要与这颗树连通。

最后，Alice 会从 $1$ 号点开始，对这棵树进行深度优先搜索，同时她会维护一个序列，搜索过程中，每遇到一个没访问过的点就将它上面的权值加入序列末尾。

Alice 希望最终序列的字典序尽可能小，Bob 希望最终序列的字典序尽可能大，并且他们二人都会采取最优策略。现在 Bob 请求你告诉他，最终序列会是什么样。

以下是关于字典序的定义：

• 对于一个长度为 $n$ 的序列 $a$，若 $i>n$，约定 $a_i=-\infty$。
• 对于两个序列 $a, b$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $i\ge 1$，使得 $\forall 1 \leq j < i$，$a_j = b_j$，且 $a_i < b_i$。

输入格式

在本题的部分测试点中，Bob 会把 Alice 在第一步中决定好的 $2\sim n$ 号结点的父亲告诉你。

第一行一个整数 $t$，表示子任务编号。特别地，样例的子任务编号为 $0$。

第二行一个正整数 $n$。

第三行 $2n$ 个正整数，表示排列 $a$。

第四行 $(n-1)$ 个整数，若该子任务拥有特殊性质 A，则表示 $2\sim n$ 号结点的父亲，否则这 $(n-1)$ 个整数都为 $0$。

输出格式

一行，表示最终序列。

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

10 1 4 9 7 6 5 8 3 2

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

7 1 8 2 4 6 5 3

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

2 4 8 6 7 5 3

提示

样例 #1 中，一种可能的最终树，数字为编号，括号内为权值：

数据范围

子任务	分值	$n$	特殊性质
$1$	$10$	$\le 4$	无
$2$		$\le 10^5$	B
$3$	$30$		A
$4$	$20$	$\le 3000$	无
$5$	$30$	$\le 10^5$

特殊性质 A：输入中给定一种 Alice 的最优决策中 $2\sim n$ 号结点的父亲。

特殊性质 B：$a_{n+1}\sim a_{2n}$ 构成 $1\sim n$ 的一个排列。

对于 $100\%$ 的数据，$1\le n\le 10^5$，保证序列 $a$ 是一个 $1\sim 2n$ 的排列。