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

Изначально яблоня состоит только из одного яблока - корня. Номер этого яблока равен 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".