题目描述

给你一个字符串集合 D，m 个查询，集合满足下面三个操作：
1. 向集合 D 插入字符串 s (保证不会插入之前已经插入过的字符串)；
2. 从集合 D 中删除字符串 s (保证删除的 s 一定在集合中)；
3. 询问之前存在（插入后未被删除的）的串在 S 中出现的次数，如果出现多次，计算所有次数。
请注意你应该在线解决问题，就意味着你不能同时读入整个输入。

输入格式

第一行一个整数 m；
接下来 m 行，每行一个整数 t 和字符串 s (1 \(\leq\) t \(\leq\) 3)，所有字符串 s 保证非空并且都是小写字母组成。

输出格式

输出每次查询的结果。

样例1

输入

5
1 abc
3 abcabc
2 abc
1 aba
3 abababc

输出

2
2

样例2

输入

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

输出

3
2
1
0

数据范围

对于 30%的数据，1 \(\leq\) m \(\leq\) 100，1 \(\leq\) t \(\leq\) 3， 1 \(\leq\) |s| \(\leq\) 100；
对于 100%的数据，1 \(\leq\) m \(\leq\) 3 \(\times\) \(10^5\)，1 \(\leq\) t \(\leq\) 3，1 \(\leq\) |s| \(\leq\) 3 \(\times\) \(10^5\)。

限制

3s, 768M

样例解释

样例 1：
查询 1：字符串 abc 在 s 中出现两次，输出 2；
查询 2：字符串 aba 在 s 中出现两次，输出 2。

来源

Codeforces710F
CWOI新高二专题测试十五