Lexicographically Minimal Rotation Index for Balloon Arrangement

During the prelude of a celebration, Martians prepare balloons that are tied together on a rope. The sequence of balloons can be represented as a string S of lowercase letters of length n. As the show progresses, for each performance the Martians take the next balloon (i.e. the next character in S) and add it to the celebration ring in the order given by S. Before the performance begins, they rearrange the balloons on the ring to achieve the most beautiful configuration.

For a given string T (which in our case is a prefix of S), a rotation T_i is defined as:

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

where :: denotes string concatenation. The Martians judge the beauty of a configuration by reading the balloons in the rope direction from the ring. The most beautiful configuration is the lexicographically smallest among T₁, T₂, …, T_|T|. In case there are multiple rotations that are lexicographically smallest, they prefer the one that is closest to the rope head; formally, define

$$f(T)=\min\{i \mid 1 \le i \le |T| \text{ and } T_i = \min\{T_1, T_2, \ldots, T_{|T|}\}\}. $$

Your task is to help the Martians arrange the balloons in the most beautiful order. For each prefix S[1…i] of the input string S, compute f(S[1…i]).

inputFormat

A single line containing a string S consisting of lowercase English letters.

outputFormat

Output the values of f(S[1…i]) for each i (1 ≤ i ≤ |S|) in order, separated by spaces.

sample

a

1