Путешествуя по вселенной игр, Ральф и Ванилопа обнаружили удивительную игру. В этой игре необходимо очень быстро считать, что очень им понравилось. Действие игры происходит вокруг волшебной яблони.
Изначально яблоня состоит только из одного яблока — корня. Номер этого яблока равен 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».