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 si < ti and sj = tj for all j < i. Or if such i does not exist and the string s is shorter than string t.

Here si 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 105. The codes of all symbols in the text range from 32 to 127.

Output

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