← 返回题目列表

Codeforces · 710/F

F. 字符串集查询

中文机器翻译题面 查看原题

您应该对一组 D 个字符串处理 m 个查询。每个查询都是以下三种查询之一:

1、将字符串s添加到集合D中。保证字符串s之前没有添加过。
2、从集合D中删除字符串s。保证字符串s在集合D中。
3. 对于给定的字符串 s,找出集合 D 中字符串出现的次数。如果 D 中的某个字符串 p 在 s 中出现了多次,则应该对它们全部进行计数。

请注意,您应该以在线模式解决该问题。这意味着您无法一次读取整个输入。只有在写完第三种类型的最后一个查询的答案后,您才能阅读每个查询。每次编写程序后,请使用 C++ 中的 fflush 函数和 Java 语言中的 BufferedWriter.flush 函数。

输入

第一行包含整数 m (1 ≤ m ≤ 3·105) — 查询数。

接下来的 m 行中的每一行都包含整数 t (1 ≤ t ≤ 3) 和非空字符串 s — 查询的类型和要处理的字符串。所有字符串仅由小写英文字母组成。

输入中所有字符串的长度总和不会超过 3·105。

输出

对于第三类的每个查询,打印唯一的整数 c — 字符串 s 中所需的出现次数。

示例

输入 #1

5
1 abc
3 abcabc
2 abc
1 aba
3 abababc

输出 #1

2
2

输入 #2

10
1 abc
1 bcd
1 abcd
3 abcd
2 abcd
3 abcd
2 bcd
3 abcd
2 abc
3 abcd

输出 #2

3
2
1
0