Module: 해싱

Problem

이미 제 13 회 국제 올림피아드에 참가한 Konstantin은 기차로 집으로 돌아 왔습니다. 그는 언제나처럼 앉아서 삶의 의미에 대해 생각하면서 동시에 프로그래밍 문제를 해결했습니다. 얼마 후 콘스탄틴은 졸았지만 문제는 깨어나기 위해 머리에 떠오른 문제를 해결해야 한다는 것입니다!

이번에 콘스탄틴은 처음에는 숫자가 1인 정점 하나만으로 구성된 트리를 꿈꿨습니다. 그가 설정한 문제에서 새로운 정점이 트리에 점차 추가되었습니다. i번째 초에 i+1이라는 숫자가 있는 정점이 트리에 추가되었으며 정점 p_i에서 자식으로 중단되고 정점 i+1 사이의 가장자리에 추가되었습니다. 및 p_i 문자 c_{i가 작성되었습니다.}

트리의 루트에서 정점 v까지의 각 경로는 루트에서 정점 v까지의 순서대로 현재 경로의 가장자리에 쓰여진 기호를 써서 얻은 특정 문자열에 해당합니다. Konstantin은 언뜻 보기에 어려운 작업에 직면했습니다. 새 정점을 추가할 때마다 트리의 루트(정점 번호 1)에서 시작하여 다른 정점에서 끝나는 고유 문자열의 수를 세는 것입니다. 

그의 꿈에서 Konstantin은 전혀 천재가 아니므로 스스로이 문제를 해결할 수 없습니다. Konstantin이 문제를 해결하고 깨어날 수 있도록 도와주세요.

입력:
첫 번째 줄에는 트리에 새 노드를 추가하기 위한 요청 수인 n이 포함됩니다(1 <= n <= 300000).
다음 n 줄은 정점 추가 요청을 설명합니다. i번째 쿼리는 p_i(1 <= p_i <= i) 및 c_i 매개변수로 설명됩니다. 추가된 숫자 i+1의 꼭짓점은 숫자 p_i를 가진 꼭짓점에서 자식으로 중지되고 기호 c_i가 결과 가장자리에 기록됨을 의미합니다. 라틴 알파벳의 소문자.

출력:
n 줄을 인쇄합니다. i번째 줄에 i+1번째 정점을 추가한 후 Konstantin의 문제에 대한 답을 인쇄합니다.

예:
  <몸>

입력	출력
2 1b 2p	1 2
3 1시 1시 2제	1 1 2