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