树上后缀排序

题目描述

给定一棵以 $1$ 为根包含 $n$ 个节点的树,保证对于 $2 \sim n$ 的每个节点,其父亲的编号均小于自己的编号。 每个节点上有一个的字符,一个节点所代表的字符串定义为从当前节点一直到根节点的简单路径上经过的所有字符连起来形成的字符串。 请你给这些字符串按照字典序排序。 特别地,如果两个节点所代表的字符串完全相同,它们的大小由它们父亲排名的大小决定,即谁的父亲排名大谁就更大;如果仍相同,则由它们编号的大小决定,即谁的编号大谁就更大。

输入输出格式

输入格式


第一行包含一个正整数 $n$。 第二行包含 $n-1$ 个数 $f_{2 \dots n}$,其中 $f_i$ 表示 $i$ 的父亲。 第三行为一个包含 $n$ 个**小写字母**的字符串 $s$,其中 $s_i$ 表示编号为 $i$ 的节点上的字符。

输出格式


输出一行 $n$ 个正整数,第 $i$ 个正整数表示代表**排名第 $i$ 的字符串**的节点编号。

输入输出样例

输入样例 #1

5
1 1 3 2
abbaa

输出样例 #1

1 5 4 2 3

说明

对于 $20\%$ 的数据,$n \le 10 ^ 3$。 对于 $50\%$ 的数据,$n \le 10 ^ 5$。 对于 $100\%$ 的数据,$1 \le n \le 5 \times 10 ^ 5$。