说明

有一棵包含 $N$ 个顶点的无根树，顶点编号为 $1$ 到 $N$。每个顶点上都有一枚硬币，每枚硬币上写有一个小写英文字母。

你正在进行一个收集所有 $N$ 枚硬币的游戏。你有一个初始为空的字符串 $\mathbf{S}$。你首先访问顶点 $1$，然后重复地移动到相邻的顶点。你可以访问每个顶点任意多次。每当你访问一个仍然放有硬币的顶点时，你会收集这枚硬币，并将硬币上的字母追加到 $\mathbf{S}$ 的末尾。当你访问的节点上已经没有硬币时，你什么也不做。注意，顶点 $1$ 上的硬币会最先被收集。

在收集完所有 $N$ 枚硬币后，你将得到一个长度为 $N$ 的字符串 $\mathbf{S}$。$\mathbf{S}$ 可能成为的字典序最小的字符串是什么？

输入格式

输入包含一个单独的测试用例，格式如下。

$$\begin{aligned} &N \\ &p_2 \ p_3 \ \ldots \ p_N \\ &c_1c_2 \ldots c_N \end{aligned}$$

第一行包含一个整数 $N$（$2 \leq N \leq 200,000$），表示树上的顶点数。

第二行包含 $N - 1$ 个整数。每个 $p_i$（$2 \leq i \leq N$，$1 \leq p_i < i$）表示顶点 $i$ 和 $p_i$ 是相邻的。注意，没有给出 $p_1$。

第三行包含一个由 $N$ 个小写英文字母组成的字符串。第 $i$ 个字母 $c_i$（$1 \leq i \leq N$）是顶点 $i$ 上硬币的字母。

输出格式

输出在收集完所有 $N$ 枚硬币后，$\mathbf{S}$ 可能成为的字典序最小的字符串。

7
1 1 2 2 3 3
abbabac

abababc

8
1 1 3 4 3 1 7
icpcicpc

icpccipc

提示

翻译由 DeepSeek V3.2 完成