Bobo 有一棵以节点 0 为根的树 $T$，包含 $(n + 1)$ 个节点，编号为 $0, 1, \dots, n$。树的边上关联有字符。

令 $s_i$ 为从根节点到节点 $i$ 的路径上所有字符的拼接。对于每个 $i$，Bobo 希望找到 $f_i$，使得 $s_{f_i}$ 是 $s_i$ 的最长真后缀。

注意 $s_0 = \epsilon$（空字符串）。字符串 $u$ 是 $v$ 的真后缀，当且仅当存在一个非空字符串 $w$ 使得 $wu = v$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，其中 $p_i$ 表示节点 $i$ 的父节点 ($0 \le p_i < i$)。

第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示从节点 $p_i$ 到 $i$ 的边关联的字符，该字符在字母表中的编号为 $c_i$ ($1 \le c_i \le n$)。

保证对于所有 $i \neq j$，$(p_i, c_i) \neq (p_j, c_j)$。

输出格式

输出 $n$ 个整数 $f_1, f_2, \dots, f_n$。

样例

样例输入 1

2
0 0
1 2

样例输出 1

0 0

样例输入 2

2
0 1
1 1

样例输出 2

0 1