E. Ever Forever
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hayama Mizuki is learning English and discovers an interesting linguistic pattern: the word "ever" appears as a suffix in "forever". Inspired by this, she creates a dynamic vocabulary system and poses a challenge to you.

Formally, she maintains a vocabulary list that undergoes the following operations:

  • Words can be added to or removed from the list. It is guaranteed that there are no duplicates in the vocabulary.
  • After modifications, you must determine the number of ordered pairs ($$$A$$$, $$$B$$$) where:
    • $$$A$$$ is a suffix$$$^{\text{∗}}$$$ of $$$B$$$.
    • $$$A$$$ and $$$B$$$ are distinct and both exist in the current vocabulary.

$$$^{\text{∗}}$$$A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning. For example, "ever" is a suffix of "forever", but "abc" is not a suffix of "aabbc"

Input

The first line contains one integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the number of operations that Mizuki does.

Each of the following $$$n$$$ lines contains $$$n$$$ operations. Each operation is one of the two types:

  • "$$$+$$$ $$$s$$$" — Mizuki adds word $$$s$$$ that contains only lower case Latin characters to the vocabulary. It is guaranteed that $$$s$$$ doesn't exist in the vocabulary before the operation.
  • "$$$-$$$ $$$s$$$" — Mizuki removes word $$$s$$$ from the vocabulary. It is guaranteed that $$$s$$$ exists in the vocabulary before the operation.

Note that a removed word can be readded into the vocabulary.

It is guaranteed that the sum of $$$|s|$$$ over all operations doesn't exceed $$$10^6$$$.

Output

Output $$$q$$$ integers. Each integer indicates the answer after Mizuki's each operation.

Example
Input
10
+ ever
+ never
+ forever
+ er
- never
+ rever
+ never
+ father
- er
+ mother
Output
0 1 2 5 3 6 8 9 4 4