K-Inversions

Time limit10sMemory limit512 MB

Summary

For every distance k, count pairs (i,j) with i<j, s[i]='B', s[j]='A', and j-i=k, over a string of up to a million characters.

Level: Medium7 of 10
Topics: Divide and conquer, String, Implementation, Math
Solved: No attempts yet

Problem

You are given a string $s$ made only of the upper case letters A and B. Let $n$ be its length. For an integer $k$ , a pair of indices $(i, j)$ is a $k$ -inversion when $1 \le i < j \le n$ , $s[i] = \text{B}$ , $s[j] = \text{A}$ , and $j - i = k$ .

Take the string BABA. It has two 1-inversions and one 3-inversion, and it has no 2-inversions.

For each $k$ from $1$ to $n - 1$ , report the number of $k$ -inversions in $s$ .

Input

The first line contains the string $s$ . It consists only of the upper case letters A and B, with no spaces. Its length $n$ satisfies $1 \le n \le 1\,000\,000$ .

Output

Print $n - 1$ lines, each with one integer. The first line holds the number of 1-inversions, the second line the number of 2-inversions, and so on up to the number of $(n - 1)$ -inversions. When $n = 1$ , print nothing.

Examples2

Example 1
Input
```
BABA
```
Expected output
```
2
0
1
```
Example 2
Input
```
BBBBBAAAAA
```
Expected output
```
1
2
3
4
5
4
3
2
1
```