Vào những ngày cận Tết, khi câu đối đỏ treo khắp cổng làng và từng nét chữ mang theo lời chúc an lành, học giả Lunar quyết định ghi chép lại những câu đối đặc biệt nhất trong trên cây cây nêu quanh làng.

Biết rằng tại ngôi làng H32 nơi Lunar sinh sống, cây nêu được dựng ở nhiều nơi, mỗi cây đều mang theo lời chúc và câu đối riêng. Vì H32 là một ngôi làng đặc biệt nên cây nêu của họ cũng khác thường: ta có thể mô hình hóa mỗi cây nêu thành một cây có gốc gồm ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ đến ~n~, trong đó đỉnh ~1~ là gốc của cây.

Mỗi cạnh trong cây mang theo một chữ cái thường, đại diện cho một nét chữ trong câu đối. Chuỗi các chữ cái trên một đường đi bất kỳ tạo thành một câu chữ hoàn chỉnh. Ở làng này họ gọi một chuỗi chữ là một câu đối ngày Tết nếu ta có thể sắp xếp lại các chữ cái trong chuỗi đó sao cho nó trở thành một chuỗi đối xứng (tức một palindrome). Thì câu chúc mới thực sự có ý nghĩa và mang lại nhiều may mắn cho mọi người.

Do lũ trẻ trong làng khá tinh nghịch, trên cây xuất hiện vô số câu chúc khác nhau. Nếu Lunar không ghi chép cẩn thận, cậu có thể dễ dàng nhầm lẫn giữa các câu đối. Vì vậy, Lunar cần xác định cho mỗi đỉnh ~v~ trong cây: độ dài lớn nhất của một đường đi nằm hoàn toàn trong cây con của ~v~, sao cho chuỗi các chữ cái trên đường đi đó là một câu đối ngày Tết.

Nhưng vì cây có quá nhiều nhánh nên Lunar đang rất rối và choáng váng. Vì vậy bạn hãy giúp đỡ học giả bài toán khó khăn này nhé!!

Input

• Dòng đầu tiên chứa một số nguyên ~n~ với ~(1 \leq n \leq 10^5)~

• ~n-1~ dòng tiếp theo, dòng thứ ~i~ (với ~i \ge 2~) chứa:

  • một số nguyên ~p_i~
  • một ký tự chữ thường ~c_i~. Trong đó~(1 \le p_i \le i-1),\quad c_i \in [\texttt{a}, \texttt{z}]~ ngoại trừ các chữ cái ~s, t, u, v~

  Điều này có nghĩa là tồn tại một cạnh nối giữa đỉnh ~p_i~ và đỉnh ~i~, trên cạnh đó ghi chữ cái ~c_i~.

Output

In ra ~n~ số nguyên. Số thứ ~i~ là độ dài lớn nhất của một đường đi đơn trong cây con của đỉnh ~i~, sao cho chuỗi chữ cái trên đường đi đó tạo thành một câu đối ngày Tết.

Subtask

Sample Input 1

5
1 e
1 z
3 e
3 e

Sample Output 1

3 0 2 0 0

Sample Input 2

8
1 n
2 e
3 w
4 y
5 e
6 a
7 r

Sample Output 2

1 1 1 1 1 1 1 0