JYY and his expedition team have successfully completed their mission on Mars. Before leaving, the team happened to catch the Martians' most grand annual festival, the "Balloon Festival." However, the Martians have encountered their annual problem: how to arrange the balloons most aesthetically. JYY has decided to ask you to design an algorithm to help the Martians solve this problem.

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

The figure below shows the situation of a string of balloons cbbadbcd when the 5th show is in progress. At this time, the balloons on the celebration ring are cbbad.

To make each show look better, the Martians hope to adjust the order of the balloons on the ring before each show begins, so that the arrangement of balloons for each show is the most aesthetic. For a set of balloons (a string), the Martians consider the most aesthetic string to be the lexicographically smallest string read from the celebration ring in the direction of the rope. For example, for cbbad, there are 5 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 hope to find the one closest to the end of the rope (i.e., the one with the smallest $i$). More rigorously, for a string $T$, define:

$$T_i = T[i \dots |T|] :: T[1 \dots i - 1] \quad (1 \le i \le |T|)$$

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

JYY hopes you can help him design an algorithm to make the balloon arrangement for each show as aesthetic as possible, i.e., for every prefix $S[1 \dots i]$ ($1 \le i \le |S|$) of the given string $S$, find $f(S[1 \dots i])$.

Input

The input is read from the file celebrate.in. The input file contains only one line, which includes a string $S$.

Output

The output is written to the file celebrate.out. Output one integer $f(S[1 \dots i])$ for each $i$ ($1 \le i \le |S|$) on a single line. The numbers should be separated by spaces.

Examples

Input 1

abaacaba

Output 1

1 1 1 3 3 3 6 3 8

Input 2

See celebrate/celebrate2.in and celebrate/celebrate2.ans in the contestant directory.

Subtasks