A115189.字典树模板

小明有一个单词仓库，仓库中一开始没有任何单词。

接下来会进行 $Q$ 次操作，每次操作有以下三种类型：

• 1 s：向仓库中插入一个单词 $s$；
• 2 s：查询单词 $s$ 在仓库中完整出现了多少次；
• 3 s：查询仓库中有多少个单词以 $s$ 作为前缀。

注意，同一个单词可以被插入多次，每次插入都要计入答案。

你需要对每个查询操作输出答案。

第一行输入一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行输入一个整数 $op$ 和一个字符串 $s$，表示一次操作。

其中：

• 当 $op=1$ 时，表示插入字符串 $s$；
• 当 $op=2$ 时，表示查询字符串 $s$ 完整出现了多少次；
• 当 $op=3$ 时，表示查询有多少个字符串以 $s$ 为前缀。

对于每个 $op=2$ 或 $op=3$ 的操作，输出一行一个整数，表示查询结果。

样例解释

一开始仓库为空。

插入 apple、app、apple 后，仓库中有：

• apple 出现 $2$ 次；
• app 出现 $1$ 次。

所以：

• 以 app 为前缀的单词有 apple、app、apple，共 $3$ 个；
• apple 完整出现了 $2$ 次；
• app 完整出现了 $1$ 次；
• appl 没有完整出现过，答案为 $0$。

后来插入 banana，所以：

• 以 ba 为前缀的单词有 $1$ 个；
• 以 a 为前缀的单词有 $3$ 个。

数据范围

对于所有数据，满足：

• $1\le Q\le 2\times 10^5$；
• $1\le |s|\le 50$；
• 字符串 $s$ 仅由小写英文字母组成；
• 所有输入字符串的总长度不超过 $10^6$。