K-Inversions

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.

Medium7Divide and conquerStringImplementationMathNo attempts yetTime limit10sMemory limit512 MB

Description

Examples2

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.