E. Чэн Ши и коллекции бамбуковых надписей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Слон Филимон решил сьездить к знаменитой подруге панде из Китая города Чэнду с именем Чэн Ши. Чэн Ши очень любит бамбук и показала свою коллекцию бамбуковых надписей. Каждая надпись представляет собой строку из строчных латинских букв.

Коллекция Чэн Ши — это динамическое мультимножество строк. Изначально оно пусто.

Панда может выполнять операции двух типов:

  • + s — добавить строку $$$s$$$ в мультимножество.
  • - s — удалить одну копию строки $$$s$$$ из мультимножества.

Слону Филимону стало интересно какое наименьшее количество действий потребуется после каждой операции, чтобы все строки в текущем мультимножестве стали одинаковыми.

Разрешённые действия над одной строкой из коллекции:

  1. Удаление последнего символа строки — Чэн Ши аккуратно откусывает кусочек бамбука.
  2. Добавление любого символа в конец строки — панда сажает бамбук, и он вырастает, добавляя один символ в конец.
С каждой строкой (бамбуком) можно произвести неограниченное количество действий.

Строка, к которой приводятся все остальные, может быть любой (в том числе пустой) и не обязана присутствовать в мультимножестве.

Обратите внимание: строки в мультимножестве фактически не изменяются. После каждого запроса требуется лишь вычислить минимальное количество действий, которое потребовалось бы, чтобы сделать все строки одинаковыми. Для последующих операций мультимножество остаётся неизменным.

Помогите Чэн Ши быстро отвечать на вопрос Филимона после каждого изменения.

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

В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество операций.

Каждая из следующих $$$q$$$ строк описывает одну операцию и имеет вид:

+ s или - s

где $$$s$$$ — непустая строка, состоящая из строчных латинских букв.

  • Операция + s означает добавление строки $$$s$$$ в мультимножество.
  • Операция - s означает удаление одной копии строки $$$s$$$ из мультимножества. Гарантируется, что строка $$$s$$$ присутствует в мультимножестве в момент удаления.

Во всех запросах $$$1 \le |s| \le 5 \cdot 10^5$$$. Суммарная длина всех строк во всех операциях не превышает $$$5 \cdot 10^5$$$.

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

После каждой операции выведите одно целое число — минимальное количество действий, необходимых для того, чтобы все строки текущего мультимножества стали одинаковыми.

Если после операции мультимножество пусто, выведите $$$0$$$.

Система оценки
Доп. ограничения
ГруппаБаллы$$$q$$$$$$\sum |s_i|$$$Тип операций Необходимые подгруппы
110$$$q \le 100$$$$$$\sum |s_i| \le 1000$$$+ и -–
210$$$q \le 1000$$$$$$\sum |s_i| \le 10^4$$$+ и -1
315$$$q \le 50\,000$$$$$$\sum |s_i| \le 10^5$$$+ и -1, 2
410$$$q \le 5 \cdot 10^5$$$$$$\sum |s_i| \le 5 \cdot 10^5$$$, $$$|s_i| \le 10$$$+–
510$$$q \le 5 \cdot 10^5$$$$$$\sum |s_i| \le 5 \cdot 10^5$$$, $$$|s_i| \le 10$$$+ и -4
620$$$q \le 5 \cdot 10^5$$$$$$\sum |s_i| \le 5 \cdot 10^5$$$+4
725––+ и -1–6
Пример
Входные данные
5
+ abc
+ ab
+ a
- ab
+ b
Выходные данные
0
1
2
2
4