Майлз и Питер из параллельной вселенной выкрали из лаборатории корпорации Алхемакс компьютер с секретными данными. Теперь Майлз занимается изучением его содержимого. Он открыл в терминале директорию с названием «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$$$.
Гарантируется, что в директории в один момент времени не будет двух файлов с одинаковым именем. Гарантируется, что каждый файл будет удален не более одного раза. Гарантируется, что в момент, когда Майлз задает вопрос (запрос третьего типа), файл уже добавлен в директорию, и еще не удален из нее. Гарантируется, что номер файла из запросов второго и третьего типа не превышает количество файлов, добавленных к моменту запроса.
На каждый запрос третьего типа выведите в новой строке одно число — ответ на вопрос Майлза.
Эта задача состоит из четырех подзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| 1 | 17 | $$$q \le 50$$$, $$$|s_i| \le 15$$$ | |
| 2 | 19 | $$$q \le 100$$$, $$$|s_i| \le 100$$$ | 1 |
| 3 | 31 | $$$q \le 3\,000$$$, $$$|s_i| \le 3\,000$$$ | 1, 2 |
| 4 | 33 | Без дополнительных ограничений | 1, 2, 3 |
9 + passwords + paroli ? 1 ? 2 - 1 ? 2 + parol ? 2 ? 3
3 3 1 2 1
