Игра с деревом
Путешествуя по вселенной игр, Ральф и Ванилопа обнаружили удивительную игру. В этой игре необходимо очень быстро считать, что очень им понравилось. Действие игры происходит вокруг волшебной яблони.
Изначально яблоня состоит только из одного яблока - корня. Номер этого яблока равен 1. После этого Ральф добавляет новое яблоко, которое он связывает с уже существующим с помощью ветки. На каждой ветке Ральф записывает букву латинского алфавита от a до z.
Ванилопа в свою очередь иногда срывает некоторое яблоко. Вместе с яблоком исчезает и ветка, с помощью которой оно было связано. Гарантируется, что никакое другое яблоко не подвешено к яблоку, которое сорвет Ванилопа.
Назовем словом последовательность букв на ветках, идущих от корня к яблоку. Подсловом назовем непустое количество подряд идущих букв в слове.
Вам необходимо после каждого действия посчитать количество различных подслов. Подслова считаются различными, если существуют позиции, в которых стоят различные буквы.
Входные данные
В первой строке содержится количество действий q (1 ≤ q ≤ 100000). Каждая из последующих q строк содержит описание действий в следующем формате:
1 p c (1 ≤ p ≤ n) - означает, что Ральф добавляет яблоко с минимальным положительным номером, который еще не был использован. Предком нового яблока является яблоко v, а на ветке написана латинская буква c.
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".