Suffix array

Given a string. Build the suffix array for this string. The suffix array is a lexicographically sorted array of all string suffixes. Each suffix is given by an integer - the starting position.

String s is lexicographically less than the string t, if there exists such i that s[i] < t[i] and s[j] = t[j] for all j < i. Or if such i does not exist and the string s is shorter than string t.

Here s[i] is the code of i-th symbol of string s.

Input

One line that represents the English literary text. The length of the text is no more than 10^5. The codes of all symbols in the text range from 32 to 127.

Output

Print n numbers - the suffix array of a given string.

Examples