问题描述

请你维护一个字符串集合，初始时集合为空。接下来需要处理 $Q$ 次操作，操作分为以下三种类型：

• 1 s：向集合中插入一个由小写英文字母组成的字符串 $s$（允许集合中存在相同的重复字符串）。
• 2 s：查询当前集合中以字符串 $s$ 作为前缀的字符串总个数。
• 3 s：查询当前集合中与字符串 $s$ 完全相同的字符串总个数。

输入格式

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

接下来输入 $Q$ 行，每行包含一个整数 $opt$ 和一个字符串 $s$，中间用一个空格隔开，其中 $opt \in \{1, 2, 3\}$。

输出格式

对于每次类型 $2$ 和类型 $3$ 的查询操作，输出一行一个整数表示对应的答案。

样例输入 1

8
1 apple
1 app
1 application
2 app
3 app
2 ap
1 app
3 app

样例输出 1

3
1
3
2

说明

样例 1 解释：

• 插入 apple, app, application 后，集合中包含这 $3$ 个字符串；
• 查询以 app 为前缀的字符串：apple、app、application 均满足，答案为 $3$；
• 查询与 app 完全相同的字符串：仅有 app 本身，答案为 $1$；
• 查询以 ap 为前缀的字符串：全部 $3$ 个字符串均满足，答案为 $3$；
• 再次插入 app，此时集合中包含两个 app；
• 查询与 app 完全相同的字符串，答案为 $2$。

评测数据规模

对于所有评测数据：

• $1 \leq Q \leq 10^5$
• 字符串 $s$ 仅由小写英文字母 a $\sim$ z 组成
• 单个字符串的长度满足 $1 \leq |s| \leq 100$
• 所有操作涉及的字符串总长度之和满足 $\sum |s| \leq 10^6$