D. Взлом компьютера
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Майлз и Питер из параллельной вселенной выкрали из лаборатории корпорации Алхемакс компьютер с секретными данными. Теперь Майлз занимается изучением его содержимого. Он открыл в терминале директорию с названием «SuperSecretData». Он обратил внимание, что иногда в этой директории сами по себе появляются и исчезают файлы. Имена всех файлов состоят из строчных латинских букв. В некоторые моменты его интересует, какое минимальное количество нажатий нужно сделать, чтобы ввести в терминале имя некоторого файла, который в этот момент времени находится в директории. Изначально в терминале набрана пустая строка. Майлз может нажимать на кнопки, соответствующие строчным латинским буквам, при этом, в конец строки дописывается соответствующая буква. Также, Майлз может нажимать кнопку tab. При этом, в конец строки дописываются буквы, пока очередная буква может быть определена однозначно. То есть, пока в терминале набрана строка $$$s$$$ и существует такая буква $$$c$$$, что множество файлов в директории, имена которых начинаются с $$$\overline{sc}$$$ ($$$s$$$, в конец которой дописана $$$c$$$), не отличается от множества файлов, имена которых начинаются c $$$s$$$, буква $$$c$$$ дописывается в конец строки $$$s$$$.

Например, если в директории находятся файлы «passwords» и «paroli», а в терминале набрана пустая строка, после нажатия tab, в терминале будет написано «pa». Если нажать tab еще раз, строка не изменится. Если после этого нажать «s», в терминале будет написано «pas». И если после этого нажать tab, в терминале будет написано «passwords».

Помогите Майлзу, ответьте на его вопросы.

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

В первой строке дано одно целое число $$$q$$$ — количество запросов ($$$1 \le q \le 100\,000$$$).

В следующих $$$q$$$ строках даны запросы. Каждый запрос начинается с одного символа, обозначающего тип запроса.

Если символ равен «+», запрос обозначает появление нового файла в директории, далее в этой же строке дано его имя $$$s_i$$$ ($$$1 \le |s_i| \le 100\,000$$$).

Если символ равен «-», запрос обозначает удаление файла из директории, далее в этой же строке дано целое число $$$a_i$$$ — номер файла ($$$1 \le a_i$$$). Файлы нумеруются с $$$1$$$ в порядке появления.

Если символ равен «?», запрос обозначает вопрос Майлза о том, какое минимальное количество кнопок нужно нажать, чтобы ввести имя файла, далее в этой же строке дано целое число $$$a_i$$$ — номер файла, про имя которого спрашивает Майлз ($$$1 \le a_i$$$). Файлы нумеруются с $$$1$$$ в порядке появления.

Суммарная длина всех $$$s_i$$$ не превышает $$$10^6$$$.

Гарантируется, что в директории в один момент времени не будет двух файлов с одинаковым именем. Гарантируется, что каждый файл будет удален не более одного раза. Гарантируется, что в момент, когда Майлз задает вопрос (запрос третьего типа), файл уже добавлен в директорию, и еще не удален из нее. Гарантируется, что номер файла из запросов второго и третьего типа не превышает количество файлов, добавленных к моменту запроса.

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

На каждый запрос третьего типа выведите в новой строке одно число — ответ на вопрос Майлза.

Система оценки

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

ПодзадачаБаллыОграничения Необходимые подзадачи
117$$$q \le 50$$$, $$$|s_i| \le 15$$$
219$$$q \le 100$$$, $$$|s_i| \le 100$$$1
331$$$q \le 3\,000$$$, $$$|s_i| \le 3\,000$$$1, 2
433Без дополнительных ограничений1, 2, 3
Пример
Входные данные
9
+ passwords
+ paroli
? 1
? 2
- 1
? 2
+ parol
? 2
? 3
Выходные данные
3
3
1
2
1