Problem Description

Given a tree rooted at $1$ with $n$ nodes, it is guaranteed that for every node from $2$ to $n$, the index of its parent is smaller than its own index.

Each node has a character. The string represented by a node is defined as the string formed by concatenating all characters on the simple path from the current node up to the root.

Please sort these strings in lexicographical order.

In particular, if the strings represented by two nodes are exactly the same, their order is determined by the order of their parents: the one whose parent has a larger rank is considered larger. If they are still the same, then their order is determined by their node indices: the one with the larger index is considered larger.

Input Format

The first line contains a positive integer $n$.

The second line contains $n - 1$ integers $f_{2 \dots n}$, where $f_i$ denotes the parent of node $i$.

The third line contains a string $s$ of length $n$ consisting of lowercase letters, where $s_i$ is the character on node $i$.

Output Format

Output one line with $n$ positive integers. The $i$-th integer denotes the node index that represents the string ranked $i$-th.

5
1 1 3 2
abbaa

1 5 4 2 3

Hint

For $20\%$ of the testdata, $n \le 10 ^ 3$.

For $50\%$ of the testdata, $n \le 10 ^ 5$.

For $100\%$ of the testdata, $1 \le n \le 5 \times 10 ^ 5$.

Translated by ChatGPT 5