Слон Филимон решил сьездить к знаменитой подруге панде из Китая города Чэнду с именем Чэн Ши. Чэн Ши очень любит бамбук и показала свою коллекцию бамбуковых надписей. Каждая надпись представляет собой строку из строчных латинских букв.
Коллекция Чэн Ши — это динамическое мультимножество строк. Изначально оно пусто.
Панда может выполнять операции двух типов:
Слону Филимону стало интересно какое наименьшее количество действий потребуется после каждой операции, чтобы все строки в текущем мультимножестве стали одинаковыми.
Разрешённые действия над одной строкой из коллекции:
Строка, к которой приводятся все остальные, может быть любой (в том числе пустой) и не обязана присутствовать в мультимножестве.
Обратите внимание: строки в мультимножестве фактически не изменяются. После каждого запроса требуется лишь вычислить минимальное количество действий, которое потребовалось бы, чтобы сделать все строки одинаковыми. Для последующих операций мультимножество остаётся неизменным.
Помогите Чэн Ши быстро отвечать на вопрос Филимона после каждого изменения.
В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество операций.
Каждая из следующих $$$q$$$ строк описывает одну операцию и имеет вид:
+ s или - s
где $$$s$$$ — непустая строка, состоящая из строчных латинских букв.
Во всех запросах $$$1 \le |s| \le 5 \cdot 10^5$$$. Суммарная длина всех строк во всех операциях не превышает $$$5 \cdot 10^5$$$.
После каждой операции выведите одно целое число — минимальное количество действий, необходимых для того, чтобы все строки текущего мультимножества стали одинаковыми.
Если после операции мультимножество пусто, выведите $$$0$$$.
| Доп. ограничения | |||||
| Группа | Баллы | $$$q$$$ | $$$\sum |s_i|$$$ | Тип операций | Необходимые подгруппы |
| 1 | 10 | $$$q \le 100$$$ | $$$\sum |s_i| \le 1000$$$ | + и - | – |
| 2 | 10 | $$$q \le 1000$$$ | $$$\sum |s_i| \le 10^4$$$ | + и - | 1 |
| 3 | 15 | $$$q \le 50\,000$$$ | $$$\sum |s_i| \le 10^5$$$ | + и - | 1, 2 |
| 4 | 10 | $$$q \le 5 \cdot 10^5$$$ | $$$\sum |s_i| \le 5 \cdot 10^5$$$, $$$|s_i| \le 10$$$ | + | – |
| 5 | 10 | $$$q \le 5 \cdot 10^5$$$ | $$$\sum |s_i| \le 5 \cdot 10^5$$$, $$$|s_i| \le 10$$$ | + и - | 4 |
| 6 | 20 | $$$q \le 5 \cdot 10^5$$$ | $$$\sum |s_i| \le 5 \cdot 10^5$$$ | + | 4 |
| 7 | 25 | – | – | + и - | 1–6 |
5+ abc+ ab+ a- ab+ b
0 1 2 2 4
| Название |
|---|


