Migrated from Lutece 1290 赏树的天行廖

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

神奇的电子科技大学长着一棵神奇的树。

这棵树一共有$n+1$个节点，从$0$号到$n$号，每条边上有一个字符$c_i$。

一日天行廖在校园内游历，见到这棵树，忽然想到了一个问题。

定义$s_i$为从根节点到$i$的路径所构成的字符串。

对于每个节点$i$，天行廖想知道一个数$f(i)\neq i$，使得$s_{f(i)}$是$s_i$的最长后缀。

Input

输入一个整数$1<=n<=200000$，接下来两行。

第一行$n$个整数，$p_1,p_2,\cdots,p_n$，$0<=p_i<i$，$p_i$表示$i$的父亲

第二行$n$个整数，$c_1,c_2,\cdots,c_n$，$1<=c_i<=n$，$c_i$表示$i$向其父亲连的边上的字符。

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

Output

输出$n$个数，$f(1),f(2),\cdots,f(n)$

Samples

2
0 0
1 2

0 0

2
0 1
1 1

0 1

Resources

咦咦。。。