QueryreuQ

A string is a palindrome when reading it backwards gives the same string. For example "a", "aa", "appa" and "queryreuq" are all palindromes.

You start with an empty string $S$ and process two kinds of operations.

1. Append one lowercase letter to the end of $S$.
2. Delete the last character of $S$.

After each operation, count the palindromic substrings of the current string. For a string $S$ and integers $i$, $j$ with $1 \le i \le j \le |S|$, let $S[i, j]$ be the substring of $S$ that runs from its $i$-th character to its $j$-th character. Count the pairs $(i, j)$ for which $S[i, j]$ is a palindrome, and print that count.

The input has two lines.

The first line has the number of queries $Q$.

The second line has the queries as a single string of length $Q$. Its $i$-th character $K_i$ describes the $i$-th query.

$K_i$ is either '-' or a lowercase English letter ('a', 'b', ..., 'z'). The quotation marks are not part of the input.

If $K_i$ is '-', delete the last character of $S$. If $K_i$ is a lowercase letter, append $K_i$ to the end of $S$.

The length of $S$ after every query is guaranteed to be at least 1.

Print $Q$ integers on one line, separated by a single space. The $i$-th integer is the answer after the $i$-th query.

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