Drzewa

서쪽으로 펼쳐진 지역에 $2$번부터 $n$번까지 번호가 붙은 나무 $n-1$그루가 있습니다. $1$번은 나무가 아니라 기지이며, 모든 나무보다 동쪽에 있습니다.

각 나무에서는 동쪽으로 정확히 한 개의 길이 뻗어 있어 기지 또는 다른 나무로 이어집니다. 그리고 기지에서 각 나무로 가는 경로는 정확히 하나뿐입니다. 따라서 전체 구조는 $1$번 기지를 뿌리로 하는 트리이고, 각 나무의 동쪽 길은 자신의 부모로 향하며, 서쪽으로 뻗은 길들은 자식으로 향합니다.

모든 길에는 난이도가 정해져 있으며 소문자 알파벳 하나로 나타냅니다. $a$가 가장 쉽고 $z$가 가장 어렵습니다.

임무는 어떤 나무(또는 기지)에서 출발해, 더 이상 갈 수 없을 때까지 계속 서쪽(자식 방향)으로 이동하는 것입니다. 즉 출발한 곳에서 시작해 서쪽으로 나가는 길이 없는 나무에 도착할 때까지 한 번에 한 길씩 내려갑니다. 지나온 길들의 난이도를 지나온 순서대로 이어 붙이면 그 임무의 난이도 문자열이 됩니다.

두 임무의 어려움은 각자의 난이도 문자열을 사전순으로 비교해 정합니다. 처음으로 서로 달라지는 위치에서 더 어려운(사전순으로 더 큰) 길을 지나는 임무가 더 어렵습니다. 한 임무의 문자열이 다른 임무 문자열의 앞부분과 완전히 같으면서 더 길다면, 더 긴 쪽이 더 어렵습니다. 두 임무의 난이도 문자열이 완전히 같다면, 더 작은 번호의 나무에서 끝나는 임무가 더 어렵다고 봅니다.

모든 나무와 기지 각각에 대해, 그 지점에서 시작하는 가장 어려운 임무가 어느 나무에서 끝나는지 구하세요.

첫째 줄에 정수 $n$ ($1 \le n \le 500000$)이 주어집니다.

이어지는 $n-1$개의 줄 중 $i$번째 줄($2 \le i \le n$에 대응)에는 정수 $p_i$ ($1 \le p_i \le i-1$)와 소문자 하나 $c_i$가 공백으로 구분되어 주어집니다. $p_i$는 나무 $i$에서 동쪽 길을 따라갔을 때 도착하는 나무(또는 기지)의 번호이고, $c_i$는 그 길의 난이도입니다.

$n$개의 정수 $d_1, d_2, \dots, d_n$을 각각 한 줄에 출력합니다. $d_i$는 $i$번 나무(또는 기지)에서 시작하는 가장 어려운 임무가 끝나는 나무의 번호입니다. $i$에서 서쪽으로 나가는 길이 하나도 없다면 $0$을 출력합니다.