Вася придумал задачу, в которой требовалось реализовать три операции:
Петя, прочитав условие, сказал, что это баян и многие олимпиадники знают, как решить данную задачу. Попробуйте и Вы решить её (ну или вспомнить решение).
В первой строке дано количество операций N (2 ≤ N ≤ 105).
В следующих N строках описаны сами операции. В начале каждой строки содержится целое число type (1 ≤ type ≤ 3), обозначающее тип операции. Если тип операции равен 1 или 2, то далее дана строка s (|s| ≤ 105) состоящая из строчных латинских букв, которую нужно добавить или удалить соответственно. Если тип равен 3, то далее следует одно целое число 1 ≤ k ≤ 105 — длина префикса.
Гарантируется, что суммарная длина всех строк в запросах не превышает 106.
Для каждой операции 3 типа выведите в отдельной строке количество различных префиксов длины k.
10
1 abracadabra
1 aba
3 2
3 3
1 bcad
3 2
3 3
2 aba
3 2
3 3
1
2
2
3
2
2
