Description

Before the celebration begins, the Martians prepare the balloons and string them onto a rope. The balloons, in order, can be seen as a string $S$ of length $n$ consisting of lowercase letters. Then, the Martians will add the balloons one by one, following the order of the string, onto a circular ring for the celebration, and perform a show to celebrate.

The figure below shows the situation for the balloon string cbbadbcd at the $5$-th show. At this time, the balloons on the celebration ring are cbbad.

To make each show look better, the Martians want to adjust the order of the balloons on the ring before each show starts, so that the balloon arrangement for each show is the most visually pleasing. For a set of balloons (a string), the Martians define the most visually pleasing string as the lexicographically smallest string read along the rope direction on the celebration ring. For example, for cbbad, there are $5$ possible starting positions to read the string:

• cbbad ($i=1$).

• bbadc ($i=2$).

• badcb ($i=3$).

• adcbb ($i=4$).

• dcbba ($i=5$).

If there are multiple lexicographically smallest strings, the Martians want the one closest to the rope head (i.e. the smallest $i$). More rigorously, for a string $T$, define

where $::$ denotes string concatenation. Define $f(T)$ as the smallest $i$ ($1 \leq i \leq |T|$) such that $T_i=min(T_1,T_2,……,T_{|T|})$.

JYY hopes you can help him design an algorithm so that the balloon arrangement for each show is the most visually pleasing. That is, for every prefix $S[1……i]$ ($1 \leq i \leq |S|$) of the given string $S$, compute $f(S[1……i])$.

Input Format

There is only one line of input, containing a string $S$.

Output Format

In one line, for each $i$ ($1 \leq i \leq |S|$), output an integer $f(S[1……i])$. Separate the numbers with spaces.

abaacaba

1 1 3 3 3 6 3 8

Hint

Translated by ChatGPT 5