题目描述

字符串的后缀是指从该字符串某一位置开始到末尾的所有字符组成的子串。例如，字符串 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 个用空格分隔的整数，依次表示按字典序排序 后的各后缀在原字符串中的起始位置。

样例数据

input1

BANANA

output1

6 4 2 1 5 3

input2

XINXIYUWEILAI

output2

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

数据范围与提示

对于 100% 的数据，字符串长度1≤n≤1,000。
其实，后缀排序有非常高效的算法！当然，我们不要求大家 “想出” 或掌握这个方法。