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 , you should process following two queries:
Add a lower case alphabet at the back of .
Remove a character at the back of .
After processing a query, you should count the number of palindrome substring in . For string and integers , (), represents a substring from th to th character of . You should print out the number of integer pairs where is palindrome.
输入格式
Input consists of two lines.
In the first line, , the number of queries is given.
In the second line, the query is given as string of length . th character denotes the th query. is ‘-’ or lower case alphabet (‘a’, ‘b’, …, ‘z’) (without quotes).
If the character is ‘-’, you should remove a character at the back of . If the character is lower case alphabet, you should add a character at the back of .
It is guaranteed that length of is always positive after the query.
输出格式
Print out space-separated integers in the first line. -th integer should be the answer of the th query.
