Sort Tree Path Strings

You are given a tree with n nodes rooted at node \(1\). It is guaranteed that for every node \(i\) with \(2 \le i \le n\), the parent\(\,p_i\) satisfies \(p_i < i\). Each node has an associated character. For each node, define its path string as the string formed by concatenating the characters on the simple path from that node up to the root. Formally, for a node \(i\), its string is

\(S(i)= c_i + c_{p_i} + c_{p_{p_i}} + \cdots + c_1\)

where \(c_j\) is the character at node \(j\) and for the root we define \(S(1)= c_1\). Your task is to sort all these n strings in lexicographical order.

Tie-breaking rule: If two nodes \(u\) and \(v\) have exactly the same string \(S(u)=S(v)\), then their relative order is determined by comparing the rankings of their respective parents. Specifically, the node whose parent has a higher ranking (i.e. appears later in the sorted order) is considered larger. If the parents are also tied, then the node with the larger node number is considered larger. Notice that since the parent's string is a suffix of its child's string, when the strings are identical the tie ultimately comes down to the node numbers.

inputFormat

The input begins with a single integer \(n\) (\(1 \le n \le 10^5\)) on the first line, representing the number of nodes in the tree. The next line contains \(n-1\) space‐separated integers. The \(i\)th integer (for \(i=2,3,\dots,n\)) denotes the parent of node \(i\) (remember that for any node \(i\ge2\), its parent is strictly less than \(i\)). The last line contains a string of length \(n\) consisting of English letters. The \(i\)th character of this string is the character associated with node \(i\).

outputFormat

Output n lines. The \(i\)th line should contain one of the sorted strings. The sorting is done in lexicographical order using the following order:

• First, by the string \(S(i)\) itself.
• If two strings are identical, then the node whose parent's ranking is lower (i.e. the parent appears earlier in the sorted order) comes first. (Equivalently, the one whose parent's ranking is higher is considered larger.)
• If the tie still persists, then the node with the smaller node number comes first.

Note: In practice, because the parent's string is a suffix of the child’s string, if \(S(u)=S(v)\) then the tie-break reduces to comparing the node numbers.

sample

3
1 1
abc

a
ba
ca