说明

这是一道模板题。

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

输入格式

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

输出格式

第一行 $n$个整数，第 $i$个整数为 $SA[i]$。

样例

ababa

5 3 1 4 2

提示

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