Problem
Khi Konstantin, sau khi tham gia Olympic tiếp theo, đã là Olympic quốc tế lần thứ 13, đang trở về nhà bằng tàu hỏa. Anh ấy, như mọi khi, ngồi và suy nghĩ về ý nghĩa của cuộc sống, đồng thời giải các bài toán lập trình. Một lúc sau, Konstantin ngủ gật, nhưng vấn đề là, để tỉnh dậy, anh phải giải quyết vấn đề nảy ra trong đầu và ám ảnh anh!
Lần này, Konstantin mơ thấy một cái cây ban đầu chỉ gồm một đỉnh mang số 1. Trong bài toán ông đặt ra, các đỉnh mới dần dần được thêm vào cây. Trong giây thứ i, một đỉnh có số i+1 được thêm vào cây, đỉnh này được treo dưới dạng con từ đỉnh p
i và trên cạnh giữa các đỉnh i+1 và p
i chữ cái c
i đã được viết.
Mỗi đường đi từ gốc của cây đến đỉnh v tương ứng với một chuỗi nào đó thu được bằng cách viết ra các ký hiệu được viết trên các cạnh của đường đi hiện tại theo thứ tự từ gốc đến đỉnh v. Thoạt nhìn, Konstantin đối mặt với một nhiệm vụ khó khăn - sau mỗi lần thêm một đỉnh mới, hãy đếm số chuỗi duy nhất bắt đầu từ gốc của cây (đỉnh số 1) và kết thúc ở một số đỉnh khác.
Trong giấc mơ của mình, Konstantin không phải là một thiên tài, vì vậy bản thân anh ta không thể giải quyết vấn đề này. Giúp Konstantin giải quyết vấn đề và thức dậy.
Đầu vào:
Dòng đầu tiên chứa số n - số lượng yêu cầu thêm nút mới vào cây (1 <= n <= 300000).
N dòng tiếp theo mô tả các yêu cầu thêm đỉnh. Truy vấn thứ i được mô tả bằng các tham số p
i (1 <= p
i <= i) và c
i, trong đó có nghĩa là đỉnh có số i+1 được thêm vào bị treo khỏi đỉnh có số p
i khi còn nhỏ và ký hiệu c
i được viết trên cạnh kết quả - một chữ thường của bảng chữ cái Latinh.
Đầu ra:
In n dòng. Trên dòng thứ i in đáp án cho bài toán Konstantin sau khi thêm đỉnh thứ i+1.
Ví dụ:
| Đầu vào |
Đầu ra |
2
1 b
2p |
1
2 |
3
1 giờ
1 giờ
2 j |
1
1
2 |