{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/xcjot9ob.png)"},{"iden":"statement","content":"令 $S_0=\\varnothing$，维护一个数据结构，要求支持以下操作：\n- `1 hoc s`，令 $S_i=S_{hoc}\\cup\\{s\\}$，其中 $s$ 是字符串（保证操作前 $s\\notin S_{hoc}$） .\n- `2 hoc s`，令 $S_i=S_{hoc}$，并查询 $S_i$ 中的所有字符串在给出的字符串 $s$ 中出现的次数之和 ."},{"iden":"input","content":"第一行包含一个正整数 $q$，表示询问次数 .\n\n接下来 $q$ 行，每行一个操作，格式见题目描述 ."},{"iden":"output","content":"对于每个操作 2，输出一行答案 ."},{"iden":"note","content":"### 样例解释\n\n第三行中，询问版本 $0$ 中的串在 `abc` 中出现几次，因为版本 $0$ 为空，所以出现 $0$ 次 .\n\n第五行中，询问版本 $3$ 中的串在 `defg` 中出现几次，因为版本 $3$ 有字符串 `def`，所以出现 $1$ 次 .\n\n第六行中，询问版本 $1$ 中的串在 `abcd` 中出现几次，因为版本 $1$ 有字符串 `abc`，所以出现 $1$ 次 .\n\n### 数据范围及约定\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：} \\displaystyle \\sum|s_i|\\le 1000$；\n- $\\texttt{Subtask 2(20 pts)：}$所有添加的字符串长度相同；\n- $\\texttt{Subtask 3(20 pts)：}$所有添加的字符串只包含一种字符；\n- $\\texttt{Subtask 4(20 pts)：}q\\le 10^3$；\n- $\\texttt{Subtask 5(30 pts)：}$无特殊限制。\n\n对于全部数据，$1\\le q\\le  5\\times10^5$，$\\displaystyle 1\\le \\sum_i|s_i|\\le 10^6$ . 所有字符串仅含小写字母 ."}],"translated_statement":null,"sample_group":[["5\n1 0 abc\n2 0 abc\n1 2 def\n2 3 defg\n2 1 abcd","0\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}