对字符串 t ，规定下标从 1 开始，定义后缀 i (编号为 i 的后缀)为 t 从下标 i 开始到字符串结束的一段子字符串。如 lr580 的后缀 3 为 580 。 定义后缀之间的大小关系为字典序，例如 0 < 580 < 80 < lr580 < r580 是 lr580 的所有后缀的大小关系。定义数组 sa[i] ，表示排序后第 i 小后缀的编号为 sa[i] 。定义数组 rk[i] 表示后缀 i 排在第 rk[i] 名。
输入
输入一行一个字符串 t ，长度满足 1\le |t| \le 1000 ，只由大小写英文和数字组成。
输出
输出第一行包含 |t| 个整数，第 i 个整数代表 sa[i] 。
输出第二行包含 |t| 个整数，第 i 个整数代表 rk[i] 。
样例
| 标准输入 复制文本 |
lr580 |
| 标准输出 复制文本 |
5 3 4 1 2 4 5 2 3 1 |
提示
本题强化版见洛谷 P3809