题目背景

题目描述

令 $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$ . 所有字符串仅含小写字母 .