Suffix Array Construction

Given a non-empty string s consisting only of lowercase English letters, your task is to construct its suffix array.

The suffix array is an array of integers giving the starting positions of all suffixes of s arranged in lexicographical order. For example, if s = "banana", then its suffixes are:

• "banana" (index 0)
• "anana" (index 1)
• "nana" (index 2)
• "ana" (index 3)
• "na" (index 4)
• "a" (index 5)

After sorting these suffixes lexicographically, the order of their starting indices is [5, 3, 1, 0, 4, 2].

Constraints: \(1 \leq |s| \leq 10^5\).

Note: If there are multiple identical suffixes, their order in the suffix array is determined by their starting index in s.

inputFormat

The input consists of a single string s read from standard input. The string contains only lowercase English letters.

outputFormat

Output the suffix array as a sequence of space-separated integers on a single line, representing the starting indices of the sorted suffixes.## sample

banana

5 3 1 0 4 2