E. Cheng Shi and the Collection of Bamboo Inscriptions
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Elephant Filimon decided to visit his panda-friend Cheng Shi from Chengdu, China. Cheng Shi loves bamboo and showed her collection of bamboo inscriptions. Each inscription is a string of lowercase Latin letters.

Cheng Shi's collection is a dynamic multiset of strings. Initially, it is empty.

The panda can perform operations of two types:

  • + s — add the string $$$s$$$ to the multiset.
  • - s — remove one copy of the string $$$s$$$ from the multiset.

Elephant Filimon became curious about the minimum number of actions required after each operation to make all strings in the current multiset identical.

Allowed actions on one string from the collection:

  1. Remove the last character of the string — Cheng Shi carefully bites off a piece of bamboo.
  2. Add any character to the end of the string — the panda plants bamboo, and it grows, adding one character to the end.
An unlimited number of actions can be performed on each string (bamboo).

The string to which all others are brought can be any (including empty) and does not have to be present in the multiset.

Note: The strings in the multiset are not actually changed. After each query, it is only necessary to compute the minimum number of actions required to make all strings identical. For subsequent operations, the multiset remains unchanged.

Help Cheng Shi quickly respond to Filimon's question after each change.

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — the number of operations.

Each of the following $$$q$$$ lines describes one operation and has the form:

+ s or - s

where $$$s$$$ is a non-empty string consisting of lowercase Latin letters.

  • The operation + s means adding the string $$$s$$$ to the multiset.
  • The operation - s means removing one copy of the string $$$s$$$ from the multiset. It is guaranteed that the string $$$s$$$ is present in the multiset at the time of removal.

In all queries, $$$1 \le |s| \le 5 \cdot 10^5$$$. The total length of all strings in all operations does not exceed $$$5 \cdot 10^5$$$.

Output

After each operation, output a single integer — the minimum number of actions required to make all strings in the current multiset identical.

If the multiset is empty after the operation, output $$$0$$$.

Scoring
Additional constraints
SubgroupPoints$$$q$$$$$$\sum |s_i|$$$Type of operations Required subgroups
110$$$q \le 100$$$$$$\sum |s_i| \le 1000$$$+ and -–
210$$$q \le 1000$$$$$$\sum |s_i| \le 10^4$$$+ and -1
315$$$q \le 50\,000$$$$$$\sum |s_i| \le 10^5$$$+ and -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$$$+ and -4
620$$$q \le 5 \cdot 10^5$$$$$$\sum |s_i| \le 5 \cdot 10^5$$$+4
725––+ and -1–6
Example
Input
5
+ abc
+ ab
+ a
- ab
+ b
Output
0
1
2
2
4