Игра с деревом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Путешествуя по вселенной игр, Ральф и Ванилопа обнаружили удивительную игру. В этой игре необходимо очень быстро считать, что очень им понравилось. Действие игры происходит вокруг волшебной яблони.

Изначально яблоня состоит только из одного яблока — корня. Номер этого яблока равен 1. После этого Ральф добавляет новое яблоко, которое он связывает с уже существующим, с помощью ветки. На каждой ветке Ральф записывает букву латинского алфавита от $$$a$$$ до $$$z$$$.

Ванилопа в свою очередь иногда срывает некоторое яблоко. Вместе с яблоком исчезает и ветка, с помощью которой оно было связано. Гарантируется, что никакое другое яблоко не подвешено к яблоку, которое удалит Ванилопа.

Назовем словом последовательность букв на ветках, идущих от корня к яблоку. Подсловом назовем непустое количество подряд идущих букв в слове.

Вам необходимо после каждого действия посчитать количество различных подслов. Подслова считаются различными, если существуют позиции, в которых стоят различные буквы.

Входные данные

В первой строке содержатся два целых числа $$$q$$$ — количество действий ($$$1 \leq q \leq 100\,000$$$). Каждая из последующих $$$q$$$ строк содержит описание действий в следующем формате: $$$1$$$ $$$p$$$ $$$c$$$ — означает, что Ральф добавляет яблоко с минимальным положительным номером, который еще не был использован ($$$1 \leq p \leq n$$$). Предком нового яблока является яблоко $$$v$$$, а на ветке написана латинская буква $$$c$$$. $$$2$$$ $$$v$$$ — Ванилопа срывает яблоко с номером $$$v$$$. Гарантируется, что корневое яблоко не будет сорвано, а также никакое яблоко не будет сорвано дважды.

Выходные данные

После каждого действия выведите количество различных подслов.

Пример

Входные данные
5
1 1 a
1 1 b
1 1 a
1 4 c
2 3
Выходные данные
1
2
2
4
3

Примечание

После первой операции есть слово «a». Различные подслова: «a».

После второй операции слова «a», «b». Различные подслова: «a», «b».

После третьей операции слова «a», «b», «a». Различные подслова: «a», «b».

После четвертой операции слова «a», «b», «ac». Различные подслова: «a», «b», «ac», «c».

После пятой операции слова «a», «ac». Различные подслова: «a», «ac», «c».