Description

A string is palindrome, if the string reads the same backward and forward. For example, strings like “a”, “aa”, “appa”, “queryreuq” are all palindromes.

For given empty string $S$, you should process following two queries:

1. Add a lower case alphabet at the back of $S$.
2. Remove a character at the back of $S$.

After processing a query, you should count the number of palindrome substring in $S$. For string $S$ and integers $i$, $j$ ($1 \le i \le j \le |S|$), $S[i, j]$ represents a substring from $i$th to $j$th character of $S$. You should print out the number of integer pairs $(i, j)$ where $S[i, j]$ is palindrome.

Input Format

Input consists of two lines.

In the first line, $Q$, the number of queries is given.

In the second line, the query is given as string of length $Q$. $i$th character $K_i$ denotes the $i$th query. $K_i$ is ‘-’ or lower case alphabet (‘a’, ‘b’, …, ‘z’) (without quotes).

If the character is ‘-’, you should remove a character at the back of $S$. If the character is lower case alphabet, you should add a character $K_i$ at the back of $S$.

It is guaranteed that length of $S$ is always positive after the query.

Output Format

Print out $Q$ space-separated integers in the first line. $i$-th integer should be the answer of the $i$th query.

17
queryreuq---------

1 2 3 4 5 7 9 11 13 11 9 7 5 4 3 2 1

Hint

Constraints

• $1 \le Q \le 10,000$