题目描述

DQS 的自家阳台上种着一棵颗粒饱满、颜色纯正的 trie。

DQS 的 trie 非常的奇特，它初始有 $n_0$ 个节点，$n_0-1$ 条边，每条边上有一个字符。并且，它拥有极强的生长力：某个 $i$ 时刻，某个节点就会新生长出一颗子树，它拥有 $s_i$ 个节点且节点之间的边上有一个字符，并且新生长出来的子树也是一个树结构。然而因为是新长出来的，根据生活常识可知 $s_i$ 必定不会大于 $i$ 时刻之前的树的大小。

DQS定义 trie 的子串为从根节点（$1$ 号节点）往下走到所有节点所构成的字符串的所有的后缀。DQS 身为一个单身 doge，常常取出其中一个子串送给妹子，然而他并不希望送给妹子两个相同的子串，所以他非常关心当前 trie 的本质不同的子串数目。

DQS 有时还会去商店购买子串，若他在商店看上某个子串，他希望得知这个子串是否在自家阳台的 trie 上已经出现，若出现则出现了多少次。如果出现了，他就可以直接回家取 trie 上的子串辣！

然而 DQS 身为一个蒟蒻，看着自家阳台的 trie 树一天天在长大，他被如此众多的节点弄得眼花缭乱，于是他找到了 IOI2016Au 的你。他会告诉你自家 trie 树的成长历程，他希望你能够对于每一次询问都做出正确回复。

输入格式

第一行输入一个整数 $\text{id}$，代表测试点编号。

接下来一行输入一个整数 $n_0$，表示初始树的大小。

接下来 $n_0-1$ 行，每行两个整数 $u,v$ 和一个字符 $c$，表示 $u$ 号节点和 $v$ 号节点之间有一条边，边上的字母为 $c$。

接下来输入 $m$，表示有 $m$ 组操作。

对于每一组，第一行输入一个整数 $\text{opt}$。

若 $\text{opt}=1$，则是一组询问，询问当前 trie 的本质不同的子串数目是多少。

若 $\text{opt}=2$，则后面跟两个整数 $rt,s_i$，表示以点 $rt$ 为根向下长出一个子树，大小为 $s_i$。

接下来 $s_i-1$ 行，每行两个整数 $u,v$ 和一个字符 $c$，表示 $u$ 号节点和 $v$ 号节点之间有一条边，边上的字母为 $c$。若长出子树之前当前树的大小是 $n$，则这 $s_i-1$ 个点的编号分别为 $n+1,n+2…n+s_i-1$。

若 $\text{opt}=3$，则是一组询问，后面输入一个字符串 $S$，询问字符串 $S$ 在当前 trie 中的出现次数。

输出格式

对于每个 $\text{opt}=1$ 或 $\text{opt}=3$，输出一行表示答案。

样例输入

1
4
1 2 a
1 3 b
2 4 b
6
1
2 2 4
2 5 b
2 6 c
5 7 b
1
3 ab
2 6 3
6 8 a
6 9 b
1

样例输出

3
7
2
11

样例说明

第一个询问，本质不同的子串是 $\texttt{a},\texttt{b},\texttt{ab}$。

第二个询问，本质不同的子串是 $\texttt{a},\texttt{b},\texttt{c},\texttt{ab},\texttt{ac},\texttt{bb},\texttt{abb}$。

第三个询问，$\texttt{ab}$ 出现次数是 $2$。

第四个询问，本质不同的子串是 $\texttt{a},\texttt{b},\texttt{c},\texttt{ab},\texttt{ac},\texttt{ca},\texttt{cb},\texttt{bb},\texttt{abb},\texttt{aca},\texttt{acb}$。

$\text{opt}=1$ 或 $\text{opt}=3$ 时对原树不做修改，只是询问。

每次 $\text{opt}=2$，会增加 $s_i-1$个节点，因为有一个节点是原树上作为新树的根出现的。

数据规模与约定

数据中，对于链的部分分，满足端点为根节点，每次新建子树都从尾部插入。

对于全部数据，保证从始至终每条边上的字符均为小写字母 $\texttt a$ 或 $\texttt b$ 或 $\texttt c$。

设 $n$ 是最终树的大小，$n,m\le10^5$，$s_i$ 不超过当前树的大小。

题目来源

By Loi_DQS