[LSOT-1] Crosspain


令 $S_0=\varnothing$，维护一个数据结构，要求支持以下操作： - `1 hoc s`，令 $S_i=S_{hoc}\cup\{s\}$，其中 $s$ 是字符串（保证操作前 $s\notin S_{hoc}$） . - `2 hoc s`，令 $S_i=S_{hoc}$，并查询 $S_i$ 中的所有字符串在给出的字符串 $s$ 中出现的次数之和 .

第一行包含一个正整数 $q$，表示询问次数 . 接下来 $q$ 行，每行一个操作，格式见题目描述 .

对于每个操作 2，输出一行答案 .

5
1 0 abc
2 0 abc
1 2 def
2 3 defg
2 1 abcd

0
1
1

### 样例解释 第三行中，询问版本 $0$ 中的串在 `abc` 中出现几次，因为版本 $0$ 为空，所以出现 $0$ 次 . 第五行中，询问版本 $3$ 中的串在 `defg` 中出现几次，因为版本 $3$ 有字符串 `def`，所以出现 $1$ 次 . 第六行中，询问版本 $1$ 中的串在 `abcd` 中出现几次，因为版本 $1$ 有字符串 `abc`，所以出现 $1$ 次 . ### 数据范围及约定 **「本题采用捆绑测试」** - $\texttt{Subtask 1(10 pts)：} \displaystyle \sum|s_i|\le 1000$； - $\texttt{Subtask 2(20 pts)：}$所有添加的字符串长度相同； - $\texttt{Subtask 3(20 pts)：}$所有添加的字符串只包含一种字符； - $\texttt{Subtask 4(20 pts)：}q\le 10^3$； - $\texttt{Subtask 5(30 pts)：}$无特殊限制。 对于全部数据，$1\le q\le 5\times10^5$，$\displaystyle 1\le \sum_i|s_i|\le 10^6$ . 所有字符串仅含小写字母 .