如果一个字符串正着读和倒着读是一样的，那么它就是一个回文串。例如，像 "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$，表示查询的数量。($1 \le Q \le 10\,000$)

第二行包含一个长度为 $Q$ 的字符串，表示查询。第 $i$ 个字符 $K_i$ 表示第 $i$ 个查询。

$K_i$ 为 '-' 或小写英文字母（'a', 'b', ..., 'z'）（不带引号）。

如果该字符为 '-'，你应该移除 $S$ 末尾的一个字符。如果该字符为小写英文字母，你应该在 $S$ 的末尾添加字符 $K_i$。

保证在每次查询后，$S$ 的长度始终为正数。

输出格式

在第一行输出 $Q$ 个空格分隔的整数。第 $i$ 个整数应当是第 $i$ 次查询后的答案。

样例

输入样例 1

17
qu-uer-ryr-reu-uq

输出样例 1

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