F. Операции над множеством строк
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам нужно обработать m запросов над множеством строк D. Каждый запрос одного из трёх типов:

  1. Добавить строку s в множество D. Гарантируется, что эта строка ранее не добавлялась в множество.
  2. Удалить строку s из множества D. Гарантируется, что эта строка находится в множестве D.
  3. Для заданной строки s найти количество вхождений строк из множества D. Если некоторая строка p из множества D имеет несколько вхождений в s вы должны посчитать их все.

Заметим, что вам требуется решить задачу в режиме online. Это значит, что вы не можете сразу считать все входные данные. Вы можете считать очередной запрос только после того как выведите ответ на последний запрос третьего типа. Используйте функции fflush в языке C++ и BufferedWriter.flush в языке Java после каждого вывода вашей программы.

Входные данные

В первой строке находится целое число m (1 ≤ m ≤ 3·105) — количество запросов.

В каждой из следующих m строк находится целое число t (1 ≤ t ≤ 3) и непустая строка s — тип запроса и строка запроса. Все строки состоят только из строчных букв английского алфавита.

Сумма длин всех строк во входных данных не превосходит 3·105.

Выходные данные

Для каждого запроса третьего типа выведите одно целое число c — требуемое количество вхождений в строку s.

Примеры
Входные данные
5
1 abc
3 abcabc
2 abc
1 aba
3 abababc
Выходные данные
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