时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

字符串的后缀是指从该字符串某一位置开始到末尾的所有字符组成的子串。例如，字符串 BANANA 的所有后缀有：

BANANA ... 起始位置为 1 的后缀
 ANANA ... 起始位置为 2 的后缀
  NANA ... 起始位置为 3 的后缀
   ANA ... 起始位置为 4 的后缀
    NA ... 起始位置为 5 的后缀
     A ... 起始位置为 6 的后缀

字符串的 "后缀排序" 是指字符串所有后缀按照字典顺序升序排序后的结果。对于 BANANA，后缀排序的结果是：

A      (6)
ANA    (4)
ANANA  (2)
BANANA (1)
NA     (5)
NANA   (3)

输入格式

一行一个仅由大写字母组成的字符串。

输出格式

假设输入字符串的长度为 $n$，输出一行，包含 $n$ 个用空格分隔的整数，依次表示按字典序排序后的各后缀在原字符串中的起始位置。

输入输出样例

样例 1

输入样例

BANANA

输出样例

6 4 2 1 5 3

样例 2

输入样例

XINXIYUWEILAI

输出样例

12 9 13 10 2 5 11 3 7 8 1 4 6

数据范围与提示

对于 $100\%$ 的数据，字符串长度 $1 \le n \le 1000$。

其实，后缀排序有非常高效的算法！当然，我们不要求大家 "想出" 或掌握这个方法。