暂无测试数据。

字符串可真令人着迷。--lyz

定义独特前缀为既是前缀，也是后缀的字符串（包括本身）。

定义字符串的独特集合为所有当前独特前缀（不包含空串）构成的集合。

最初时，拥有一个空字符串和空独特集合，现在有 $n$ 个操作：

• $1\ c\ l\ r$，表示在当前字符串最后插入字符 $c$。
• $2\ x\ l\ r$，表示回退到进行完第 $x$ 次操作后的字符串。

对于每一次操作，你需要输出当前字符串的独特集合中字符串长度 $len \in [l, r]$ 的元素个数 。

输入格式

第一行给定正整数 $n$。

接下来 $n$ 行，每一行的输入如上述所示。

所有数据不保证 $l, r$ 不超过当前字符串长度，但保证 $l \le r \le n$，对于超出当前字符串长度的部分，一律不计入贡献。

所有数据保证 $c$ 为小写字母。

输出格式

共 $n$ 行，每一行输出第 $i$ 次操作后字符串的独特集合中字符串长度 $len \in [l, r]$ 的元素个数。

数据范围

对于 $20\%$ 的数据，有 $n \le 2000, c \in [a, z], \text{op} \in \{1, 2\}$。

对于另外 $20\%$ 的数据，有 $n \le 10^5, c \in [a, b], \text{op} \in \{1, 2\}$。

对于另外 $15\%$ 的数据，有 $n \le 10^5, c \in [a, z], \text{op} \in \{1\}$。

对于另外 $15\%$ 的数据，有 $n \le 10^5, c \in [a, z], \text{op} \in \{1, 2\}, l = r$。

对于 $100\%$ 的数据，有 $1\leq n \le 2 \times 10^5, 1\leq l \leq r \leq n,c \in [a, z], \text{op} \in \{1, 2\}$。

5
1 a 1 1
1 a 1 2
1 a 2 3
1 a 2 3
1 b 1 1

1
2
2
2
0

6
1 a 1 3
1 a 1 3
2 1 1 3
1 b 1 3
2 2 1 3
1 a 1 3

1
2
1
1
2
3