CF207C1.Game with Two Trees

The Smart Beaver from ABBYY has come up with a new developing game for children. The Beaver thinks that this game will help children to understand programming better.

The main object of the game is finite rooted trees, each of their edges contains some lowercase English letter. Vertices on any tree are always numbered sequentially from 1 to m, where m is the number of vertices in the tree. Before describing the actual game, let's introduce some definitions.

We'll assume that the sequence of vertices with numbers _v_1, _v_2, ..., v__k (k ≥ 1) is a forward path, if for any integer i from 1 to k - 1 vertex v__i is a direct ancestor of vertex v__i + 1. If we sequentially write out all letters from the the edges of the given path from _v_1 to v__k, we get some string (k = 1 gives us an empty string). We'll say that such string corresponds to forward path _v_1, _v_2, ..., v__k.

We'll assume that the sequence of tree vertices with numbers _v_1, _v_2, ..., v__k (k ≥ 1) is a backward path if for any integer i from 1 to k - 1 vertex v__i is the direct descendant of vertex v__i + 1. If we sequentially write out all the letters from the edges of the given path from _v_1 to v__k, we get some string (k = 1 gives us an empty string). We'll say that such string corresponds to backward path _v_1, _v_2, ..., v__k.

Now let's describe the game that the Smart Beaver from ABBYY has come up with. The game uses two rooted trees, each of which initially consists of one vertex with number 1. The player is given some sequence of operations. Each operation is characterized by three values (t, v, c) where:

• t is the number of the tree on which the operation is executed (1 or 2);
• v is the vertex index in this tree (it is guaranteed that the tree contains a vertex with this index);
• c is a lowercase English letter.

The actual operation is as follows: vertex v of tree t gets a new descendant with number m + 1 (where m is the current number of vertices in tree t), and there should be letter c put on the new edge from vertex v to vertex m + 1.

We'll say that an ordered group of three integers (i, j, q) is a good combination if:

• 1 ≤ i ≤ _m_1, where _m_1 is the number of vertices in the first tree;
• 1 ≤ j, q ≤ _m_2, where _m_2 is the number of vertices in the second tree;
• there exists a forward path _v_1, _v_2, ..., v__k such that _v_1 = j and v__k = q in the second tree;
• the string that corresponds to the forward path in the second tree from vertex j to vertex q equals the string that corresponds to the backward path in the first tree from vertex i to vertex 1 (note that both paths are determined uniquely).

Your task is to calculate the number of existing good combinations after each operation on the trees.

ABBYY 的聪明海狸为儿童设计了一款全新的益智游戏。海狸认为，这款游戏将有助于儿童更好地理解编程。

本游戏的核心对象是有限有根树，其中每条边都标有一个小写英文字母。任意一棵树的顶点始终按顺序编号为 $1$ 到 $m$，其中 $m$ 是该树的顶点总数。在正式描述游戏规则之前，我们先引入一些定义。

我们称一个顶点序列 $v_1, v_2, \dots, v_k$（其中 $k \geq 1$）为一条正向路径（forward path），当且仅当对每个整数 $i \in [1, k-1]$，顶点 $v_i$ 都是顶点 $v_{i+1}$ 的直接祖先。若我们按从 $v_1$ 到 $v_k$ 的顺序依次写出该路径上所有边所对应的字母，则得到某个字符串（当 $k = 1$ 时，该字符串为空串）。我们称此字符串对应于正向路径 $v_1, v_2, \dots, v_k$。

我们称一个顶点序列 $v_1, v_2, \dots, v_k$（其中 $k \geq 1$）为一条反向路径（backward path），当且仅当对每个整数 $i \in [1, k-1]$，顶点 $v_i$ 都是顶点 $v_{i+1}$ 的直接后代。若我们按从 $v_1$ 到 $v_k$ 的顺序依次写出该路径上所有边所对应的字母，则得到某个字符串（当 $k = 1$ 时，该字符串为空串）。我们称此字符串对应于反向路径 $v_1, v_2, \dots, v_k$。

现在我们来描述 ABBYY 的聪明海狸所设计的这款游戏。游戏使用两棵有根树，初始时每棵树均只含一个编号为 $1$ 的顶点。玩家会收到一系列操作指令。每次操作由三个值 $(t, v, c)$ 描述，其中：

• $t$ 表示执行操作的树的编号（$1$ 或 $2$）；
• $v$ 表示该树中某顶点的索引（保证该树中存在编号为 $v$ 的顶点）；
• $c$ 是一个小写英文字母。

该操作的实际含义是：在树 $t$ 中，为顶点 $v$ 添加一个新后代，其编号为 $m + 1$（其中 $m$ 是树 $t$ 当前的顶点总数），并在从顶点 $v$ 指向顶点 $m + 1$ 的新边上标注字母 $c$。

我们称一个有序三元组 $(i, j, q)$ 为好组合（good combination），当且仅当满足以下全部条件：

• $1 \leq i \leq m_1$，其中 $m_1$ 是第一棵树的顶点总数；
• $1 \leq j, q \leq m_2$，其中 $m_2$ 是第二棵树的顶点总数；
• 在第二棵树中，存在一条正向路径 $v_1, v_2, \dots, v_k$，使得 $v_1 = j$ 且 $v_k = q$；
• 第二棵树中从顶点 $j$ 到顶点 $q$ 的正向路径所对应的字符串，等于第一棵树中从顶点 $i$ 到根节点（即顶点 $1$）的反向路径所对应的字符串（注意：这两条路径均由端点唯一确定）。

你的任务是：在每次对树执行操作后，计算当前已存在的“好组合”的总数。

The first line contains integer n — the number of operations on the trees. Next n lines specify the operations in the order of their execution. Each line has form "t v c", where t is the number of the tree, v is the vertex index in this tree, and c is a lowercase English letter.

To get the full points for the first group of tests it is sufficient to solve the problem with 1 ≤ n ≤ 700.

To get the full points for the second group of tests it is sufficient to solve the problem with 1 ≤ n ≤ 7000.

To get the full points for the third group of tests it is sufficient to solve the problem with 1 ≤ n ≤ 100000.

第一行包含一个整数 $n$ —— 表示对树进行的操作次数。接下来的 $n$ 行按执行顺序给出这些操作。每行的格式为 “$t$ $v$ $c$”，其中 $t$ 是树的编号，$v$ 是该树中顶点的索引，$c$ 是一个小写英文字母。

若要获得第一组测试用例的全部分数，只需解决满足 $1 \leq n \leq 700$ 的情况即可。

若要获得第二组测试用例的全部分数，只需解决满足 $1 \leq n \leq 7000$ 的情况即可。

若要获得第三组测试用例的全部分数，只需解决满足 $1 \leq n \leq 100000$ 的情况即可。

Print exactly n lines, each containing one integer — the number of existing good combinations after the corresponding operation from the input.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

精确输出 n 行，每行包含一个整数——即对应输入中每次操作后存在的“好组合”的数量。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

After the first operation the only good combination was (1, 1, 1). After the second operation new good combinations appeared, (2, 1, 2) and (1, 2, 2). The third operation didn't bring any good combinations. The fourth operation added good combination (1, 3, 3). Finally, the fifth operation resulted in as much as three new good combinations — (1, 4, 4), (2, 3, 4) and (3, 1, 4).

第一次操作后，唯一的好组合是 $(1,\,1,\,1)$。第二次操作后，出现了两个新的好组合：$(2,\,1,\,2)$ 和 $(1,\,2,\,2)$。第三次操作未带来任何好组合。第四次操作新增了好组合 $(1,\,3,\,3)$。最后，第五次操作共产生了三个新好组合：$(1,\,4,\,4)$、$(2,\,3,\,4)$ 和 $(3,\,1,\,4)$。