题目描述

给定一个大小为 $n$ 的树，它共有 $n$ 个结点与 $n - 1$ 条边，结点从 $1 \sim n$ 编号。初始时每个结点上都有一个 $1 \sim n$ 的数字，且每个 $1 \sim n$ 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 $n - 1$ 次删边操作，每次操作你必须按照小 Z 的要求选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。

$n - 1$ 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 $1 \sim n$ 所在的结点编号依次排列，就得到一个结点编号的排列 $P_i$ 。现在请你求出，在小 Z 给出的删边操作方案下能得到的 $P_i$ 。

如上图，蓝圈中的数字 $1 \sim 5$ 一开始分别在结点②、①、③、⑤、④。按照小 Z 给出的 (1)(4)(3)(2) 顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为①③④②⑤，该排列是按照小 Z 给出的删边操作方案得到的。

输入格式

第一行包含一个正整数 $n$ ，表示树的结点数。

接下来 $1$ 行，包含 $n$ 个正整数 $a_1,a_2,a_3,\cdot\cdot\cdot,a_n$ ，表示编号为 $i$ 的结点上的数字为 $a_i$ 。

接下来 $n - 1$ 行，每行包含三个正整数 $a , b , c$ ，表示编号为 $a$ 的结点与编号为 $b$ 的结点之间有一条编号为 $c$ 的边相连。

接下来 $1$ 行，包含 $n - 1$ 个正整数，按顺序给出小 Z 想要删除的边的编号。

共一行，包含 $n$ 个正整数，将数字 $1 \sim n$ 所在的结点编号依次排列，得到一个结点编号的排列 $P_i$ ，并输出。

1 3 4 2 5

此样例为上图情况，解释见题目描述中。

对于全部数据，保证 $2 \le n \le 100$ 。