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.
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.
Print n numbers - the suffix array of a given string.