Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJust in case somebody missed it: we have wonderful girls in Arpa’s land.

Arpa has a rooted tree (connected acyclic graph) consisting of *n* vertices. The vertices are numbered 1 through *n*, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

He asks Arpa, for each vertex *v*, what is the length of the longest simple path in subtree of *v* that form a Dokhtar-kosh string.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 5·10^{5}) — the number of vertices in the tree.

(*n* - 1) lines follow, the *i*-th of them contain an integer *p*_{i + 1} and a letter *c*_{i + 1} (1 ≤ *p*_{i + 1} ≤ *i*, *c*_{i + 1} is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes *p*_{i + 1} and *i* + 1 and there is a letter *c*_{i + 1} written on this edge.

Output

Print *n* integers. The *i*-th of them should be the length of the longest simple path in subtree of the *i*-th vertex that form a Dokhtar-kosh string.

Examples

Input

4

1 s

2 a

3 s

Output

3 1 1 0

Input

5

1 a

2 h

1 a

4 h

Output

4 1 0 1 0

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2018 21:34:54 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|