给定一个仅由大写字母 A 和 B 组成的字符串 $s$。对于一个整数 $k$，如果一对下标 $i$ 和 $j$ ($1 \le i < j \le n$) 满足 $s[i] = \text{B}$，$s[j] = \text{A}$ 且 $j - i = k$，则称其为一个 $k$-逆序对。

考虑字符串 BABA。它有两个 1-逆序对和一个 3-逆序对。它没有 2-逆序对。

对于 $1$ 到 $n - 1$（包含边界）之间的每个 $k$，输出字符串 $s$ 中 $k$-逆序对的数量。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。输入由一行字符串 $s$ 组成，该字符串仅包含大写字母 A 和 B。字符串 $s$ 的长度在 $1$ 到 $1,000,000$ 之间。字符串中不包含空格。

输出格式

输出 $n - 1$ 行，每行一个整数。第一行的整数应为 1-逆序对的数量，第二行为 2-逆序对的数量，依此类推。

样例

输入 1

BABA

输出 1

2
0
1

输入 2

BBBBBAAAAA

输出 2

1
2
3
4
5
4
3
2
1