Drzewa

West of the base lies an area holding $n-1$ trees numbered from $2$ to $n$. Node $1$ is not a tree but the base, and it sits east of every tree.

From each tree exactly one path leads east, to the base or to another tree, and there is exactly one route from the base to each tree. The whole structure is therefore a tree rooted at the base (node $1$): each tree's east path goes to its parent, while the paths leading west go to its children.

Every path has a difficulty written as a single lowercase letter, where $a$ is the easiest and $z$ is the hardest.

A mission starts at some tree (or the base) and keeps moving west (toward children) for as long as possible: from the starting point it goes down one path at a time until it reaches a tree that has no westward path. Writing the difficulties of the traversed paths in order gives the mission's difficulty string.

To compare two missions, compare their difficulty strings lexicographically. At the first position where they differ, the mission taking the harder (lexicographically larger) path is harder. If one string equals the beginning of the other and is longer, the longer one is harder. If two missions have identical difficulty strings, the one ending at the tree with the smaller number is considered harder.

For every tree and for the base, determine at which tree the hardest mission starting there ends.

The first line contains an integer $n$ ($1 \le n \le 500000$).

Each of the next $n-1$ lines, the $i$-th of them corresponding to $2 \le i \le n$, contains an integer $p_i$ ($1 \le p_i \le i-1$) and a lowercase letter $c_i$ separated by a space. $p_i$ is the number of the tree (or the base) reached by following the east path from tree $i$, and $c_i$ is that path's difficulty.

Print $n$ integers $d_1, d_2, \dots, d_n$, each on its own line. $d_i$ is the number of the tree at which the hardest mission starting at tree (or base) $i$ ends. If no path leads west out of $i$, print $0$.