나무 게임

랄프와 바닐로피는 게임의 우주를 여행하다가 놀라운 게임을 발견했다. 이 게임에서는 아주 빠르게 세야 하는데, 둘 다 이 점을 무척 마음에 들어 했다. 게임은 마법의 사과나무를 중심으로 진행된다.

처음에 사과나무에는 사과 하나, 즉 뿌리만 있다. 뿌리의 번호는 1이다. 이후 랄프가 새 사과를 추가하고, 이미 있는 사과와 가지로 잇는다. 랄프는 각 가지에 $a$부터 $z$까지의 라틴 알파벳 글자를 하나씩 적는다.

바닐로피는 가끔 사과를 딴다. 사과를 따면 그 사과를 잇던 가지도 함께 사라진다. 바닐로피가 따는 사과에는 다른 사과가 매달려 있지 않다고 보장된다.

단어는 뿌리에서 특정 사과까지 가는 경로의 가지에 적힌 글자를 순서대로 이은 것이다. 부분 문자열은 단어에서 연속한 글자 하나 이상으로 이루어진 구간이다.

매 동작 후에 서로 다른 부분 문자열의 개수를 구하라. 두 부분 문자열은 같은 위치에 서로 다른 글자가 있으면 다른 것으로 본다.

첫 줄에 동작의 수 $q$가 주어진다 ($1 \leq q \leq 100\,000$). 다음 $q$개의 줄에는 아래 형식 중 하나로 동작이 주어진다.

1 $p$ $c$: 랄프가 아직 사용되지 않은 가장 작은 양의 번호를 가진 사과를 추가한다. 새 사과의 부모는 사과 $p$이고, 가지에는 소문자 $c$가 적힌다. ($1 \leq p \leq n$)

2 $v$: 바닐로피가 번호 $v$인 사과를 딴다.

뿌리 사과는 따이지 않는다. 또한 같은 사과를 두 번 따는 일은 없다.

매 동작 후에 서로 다른 부분 문자열의 개수를 출력한다.

첫 번째 동작 후 단어는 <<a>>이다. 서로 다른 부분 문자열은 <<a>>이다.

두 번째 동작 후 단어는 <<a>>, <<b>>이다. 서로 다른 부분 문자열은 <<a>>, <<b>>이다.

세 번째 동작 후 단어는 <<a>>, <<b>>, <<a>>이다. 서로 다른 부분 문자열은 <<a>>, <<b>>이다.

네 번째 동작 후 단어는 <<a>>, <<b>>, <<ac>>이다. 서로 다른 부분 문자열은 <<a>>, <<b>>, <<ac>>, <<c>>이다.

다섯 번째 동작 후 단어는 <<a>>, <<ac>>이다. 서로 다른 부분 문자열은 <<a>>, <<ac>>, <<c>>이다.