题目描述

这是一道模板题。

读入一个长度为 $ n $ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $ 1 $ 到 $ n $。

输入格式

一行一个长度为 $ n $ 的仅包含大小写英文字母或数字的字符串。

输出格式

第一行 $ n $ 个整数，第 $ i $ 个整数为 $ \text{SA}[i]$。

样例数据

样例 1 输入

ababa

样例 1 输出

5 3 1 4 2

样例 2 输入

0103210002010200210200101020202222010111

样例 2 输出

7 21 8 15 22 35 11 24 1 37 19 13 9 26 28 16 30 3 40 6 23 36 18 12 25 2 39 38 20 14 34 10 27 29 5 17 33 32 31 4

子任务

Subtask 1 (25 points), $1 \leq n \leq 10^3$

Subtask 2 (25 points), $1 \leq n \leq 10^4$

Subtask 3 (25 points), $1 \leq n \leq 10^5$

Subtask 4 (25 points), $ 1 \leq n \leq 10 ^ 6 $