QueryreuQ

어떤 문자열을 뒤집었을 때 원래 문자열과 같으면 그 문자열을 팰린드롬이라고 한다. 예를 들어 "a", "aa", "appa", "queryreuq"는 모두 팰린드롬이다.

비어 있는 문자열 $S$에서 시작해 두 가지 연산을 처리한다.

1. $S$의 맨 뒤에 알파벳 소문자를 하나 붙인다.
2. $S$의 맨 뒤 문자를 하나 지운다.

연산을 하나 처리할 때마다 그 시점의 $S$에 들어 있는 팰린드롬 부분문자열의 개수를 세어야 한다. $1 \le i \le j \le |S|$인 정수 $i$, $j$에 대해 $S[i, j]$를 $S$의 $i$번째 문자부터 $j$번째 문자까지로 이루어진 부분문자열이라고 하자. $S[i, j]$가 팰린드롬인 정수쌍 $(i, j)$의 개수를 세어 출력한다.

입력은 두 줄이다.

첫째 줄에 쿼리의 개수 $Q$가 주어진다.

둘째 줄에 쿼리가 길이 $Q$인 문자열 하나로 주어진다. 이 문자열의 $i$번째 문자 $K_i$가 $i$번째 쿼리를 나타낸다.

$K_i$는 '-'이거나 영어 소문자('a', 'b', ..., 'z') 중 하나다. 따옴표는 입력에 포함되지 않는다.

$K_i$가 '-'이면 $S$의 맨 뒤 문자를 지우고, 영어 소문자면 $S$의 맨 뒤에 $K_i$를 붙인다.

각 쿼리를 처리한 뒤 $S$의 길이는 항상 1 이상임이 보장된다.

한 줄에 $Q$개의 정수를 공백 하나로 구분해 출력한다. $i$번째 정수는 $i$번째 쿼리를 처리한 뒤의 답이다.

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