Extracting Minimal Substring Starting Indices

In the half-moon night sky, countless longings between people are symbolized by a string \(S\), where \(n=|S|\). The task is to extract the essence of all these longings.

For each integer \(i\) with \(1 \leq i \leq n\), define \(Y_S(i)\) as the starting index (using 1-indexing) of the lexicographically smallest substring of \(S\) of length \(i\). In case of ties, choose the substring with the smallest starting index.

For example, for \(S=\texttt{baa}\):

• Substrings of length 1: "b", "a", "a". The lexicographically smallest is "a" (first occurring at index 2), so \(Y_S(1)=2\).
• Substrings of length 2: "ba", "aa". The lexicographically smallest is "aa" starting at index 2, so \(Y_S(2)=2\).
• Substring of length 3: "baa" starting at index 1, so \(Y_S(3)=1\).

Your task is to compute \(Y_S(i)\) for every \(1 \leq i \leq n\) given the string \(S\).

inputFormat

The input consists of a single line containing the string \(S\). The length of \(S\) is \(n\) (\(1 \leq n\)).

outputFormat

Output \(n\) space-separated integers where the \(i\)-th integer is \(Y_S(i)\), the starting index of the lexicographically smallest substring of length \(i\) in \(S\).

sample

baa

2 2 1