P3809 [Template] Suffix Sorting

This is a template problem.

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 $.

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

One line containing $ n $ integers representing the answer.

$ 1 \le n \le 10^6 $. Translated by ChatGPT 5