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

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

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

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

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

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

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

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

• 1 ≤ i ≤ m₁, где m₁ — количество вершин в первом дереве;
• 1 ≤ j, q ≤ m₂, где m₂ — количество вершин во втором дереве;
• во втором дереве существует прямой путь v₁, v₂, ..., v_k такой, что v₁ = j и v_k = q;
• строка, соответствующая прямому пути во втором дереве от вершины j до вершины q равна строке, соответствующей обратному пути в первом дереве от вершины i до вершины 1 (заметим, что оба пути единственны).

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