C1. Игра с двумя деревьями
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

Последовательность вершин дерева с номерами v1, v2, ..., vk (k ≥ 1) будем называть прямым путем, если для любого целого i от 1 до k - 1 вершина vi является непосредственным предком вершины vi + 1. Если мы последовательно выпишем все буквы по ребрам данного пути от v1 до vk, то мы получим некоторую строку (при k = 1 — пустую). Будем говорить, что такая строка соответствует прямому пути v1, v2, ..., vk.

Последовательность вершин дерева с номерами v1, v2, ..., vk (k ≥ 1) будем называть обратным путем, если для любого целого i от 1 до k - 1 вершина vi является непосредственным потомком вершины vi + 1. Если мы последовательно выпишем все буквы по ребрам данного пути от v1 до vk, то мы получим некоторую строку (при k = 1 — пустую). Будем говорить, что такая строка соответствует обратному пути v1, v2, ..., vk.

Теперь опишем игру, которую придумал Умный Бобер из ABBYY. Для игры используются два корневых дерева, каждое из которых изначально состоит из одной вершины с номером 1. Игроку дана некоторая последовательность операций. Каждая операция характеризуется тройкой (t, v, c), где:

  • t — номер дерева, с которым производится операция (1 либо 2);
  • v — номер вершины в рассматриваемом дереве (гарантируется, что дерево содержит вершину с таким номером);
  • c — некоторая строчная буква латинского алфавита.

Сама операция заключается в следующем: у вершины v дерева t появляется новый потомок с номером m + 1 (где m — текущее число вершин в дереве t), причем на ребре, которое входит в новую вершину, нужно записать букву c.

Упорядоченную тройку целых чисел (i, j, q) будем называть хорошей комбинацией, если:

  • 1 ≤ i ≤ m1, где m1 — количество вершин в первом дереве;
  • 1 ≤ j, q ≤ m2, где m2 — количество вершин во втором дереве;
  • во втором дереве существует прямой путь v1, v2, ..., vk такой, что v1 = j и vk = q;
  • строка, соответствующая прямому пути во втором дереве от вершины j до вершины q равна строке, соответствующей обратному пути в первом дереве от вершины i до вершины 1 (заметим, что оба пути единственны).

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

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

В первой строке содержится целое число n — количество операций над деревьями. Следующие n строк содержат описания операций в порядке их выполнения. Каждая строка имеет вид «t v c», где t — номер дерева, v — номер вершины в дереве, c — строчная буква латинского алфавита.

Для получения полного балла за первую группу тестов достаточно решить задачу при 1 ≤ n ≤ 700.

Для получения полного балла за вторую группу тестов достаточно решить задачу при 1 ≤ n ≤ 7000.

Для получения полного балла за третью группу тестов достаточно решить задачу при 1 ≤ n ≤ 100000.

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

Выведите ровно n строк по одному целому числу в каждой — количество существующих хороших комбинаций после соответствующей операции из ввода.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a
Выходные данные
1
3
3
4
7
Примечание

После первой операции единственная хорошая комбинация — (1, 1, 1). После второй операции появились новые хорошие комбинации (2, 1, 2) и (1, 2, 2). Третья операция не принесла никаких хороших комбинаций. После четвёртой операции появилась хорошая комбинация (1, 3, 3). Наконец, после пятой операции появилось сразу три новых хороших комбинации — (1, 4, 4), (2, 3, 4) и (3, 1, 4).