Prefix Array

A suffix array is what you get by sorting every suffix of a string in lexicographic order and then writing down, in that order, the index where each suffix starts. Take the string 'banana'.

1. The suffixes of 'banana' are banana, anana, nana, ana, na, a, six in total.
2. Sorted lexicographically they come out as a, ana, anana, banana, na, nana.
3. Writing the starting index of each one in that order gives 5, 3, 1, 0, 4, 2.

So the suffix array of 'banana' is {5, 3, 1, 0, 4, 2}.

Taekhee and Namgyu, members of the problem solving club Morgorithm at Yonsei University, were working through a string problem together. Here is part of the conversation.

• Taekhee: can't we just build the suffix array and solve it from there?
• Namgyu: suffix array.. so I build the prefix array and reverse it?
• Taekhee: ??
• Namgyu: ??
• Taekhee: a suffix is the tail of the string.
• Namgyu: oh, right.. I read it as prefix.
• Taekhee: but then how do you build a prefix array?
• Namgyu: good point.
• Taekhee: reverse the string and build a suffix array? no, that isn't it..

The two of them got stuck. Write the program that builds the prefix array for them.

The first line contains a string $S$ made of lowercase English letters. ($1 \le |S| \le 100000$)

Print $|S|$ lines. Sort every prefix of $S$ in lexicographic order, then print the index where each prefix ends, from the first prefix in that order to the last. Indices into the string start at 0.