您应该对一组 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