说明

如果一个字符串正读和反读都相同，则称其为回文串。例如，像 “a”、“aa”、“appa”、“queryreuq” 这样的字符串都是回文串。

对于一个给定的初始为空字符串 $S$，你需要处理以下两种操作：

1. 在 $S$ 的末尾添加一个小写字母。
2. 删除 $S$ 末尾的一个字符。

在处理完每次操作后，你需要计算 $S$ 中回文子串的数量。对于字符串 $S$ 和整数 $i$, $j$（$1 \le i \le j \le |S|$），$S[i, j]$ 表示 $S$ 中从第 $i$ 个到第 $j$ 个字符构成的子串。你需要输出满足 $S[i, j]$ 是回文串的整数对 $(i, j)$ 的数量。

输入格式

输入包含两行。

第一行给出一个整数 $Q$，表示操作的数量。

第二行给出一个长度为 $Q$ 的字符串来描述所有操作。第 $i$ 个字符 $K_i$ 表示第 $i$ 次操作。$K_i$ 是 ‘-’ 或小写字母（‘a’, ‘b’, …, ‘z’）（不包含引号）。

如果字符是 ‘-’，则你应该删除 $S$ 末尾的一个字符。如果字符是小写字母，则你应该将字符 $K_i$ 添加到 $S$ 的末尾。

保证每次操作后 $S$ 的长度始终为正数。

输出格式

在第一行输出 $Q$ 个由空格分隔的整数。第 $i$ 个整数应该是第 $i$ 次操作后的答案。

17
queryreuq---------

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

提示

数据范围

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