【模板】后缀排序

题目背景

这是一道模板题。

题目描述

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

输入输出格式

输入格式


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

输出格式


一行,共n个整数,表示答案。

输入输出样例

输入样例 #1

ababa

输出样例 #1

5 3 1 4 2

说明

$n <= 10^6$