405139: GYM101806 Q QueryreuQ

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 ≤ i ≤ j ≤ |S|), represents a substring from ith to jth character of S. You should print out the number of integer pairs (i,  j) where is palindrome.

Input consists of two lines.

In the first line, Q, the number of queries is given. (1 ≤ Q ≤ 10, 000)

In the second line, the query is given as string of length Q. ith character K_i denotes the ith 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.

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

17
qu-uer-ryr-reu-uq

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