Description

Read a string of length $n$ consisting of uppercase and lowercase English letters or digits. Sort all its non-empty suffixes in ascending lexicographic order (compared by ASCII values), then output, in that order, the position in the original string of the first character of each suffix. Positions are numbered from $1$ to $n$.

Input Format

A single line containing a string of length $n$ consisting only of uppercase and lowercase English letters or digits.

Output Format

One line containing $n$ integers representing the answer.

ababa

5 3 1 4 2

Hint

$1 \le n \le 10^6$.

Translated by ChatGPT 5