Suffix Array Indexes

Given a string S of length \( n \) consisting of uppercase letters, lowercase letters, or digits, generate all its non-empty suffixes. Sort these suffixes in lexicographical order based on ASCII values. Then, output the starting position (1-indexed) of the first character of each suffix in the original string, following the sorted order.

Note: A suffix of the string S starting at position \( i \) is defined as \( S[i..n] \) for \( 1 \le i \le n \).

inputFormat

The input contains a single line with the string \( S \) (composed of uppercase letters, lowercase letters or digits).

outputFormat

Output a single line containing \( n \) integers separated by spaces. Each integer represents the starting position in the original string of the corresponding suffix after the suffixes have been sorted in lexicographical (ASCII) order.

sample

bca

3 1 2