作业已超过截止时间，您无法递交本题目。

Background

Special for beginners, ^_^

Description

这是一道模板题。

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

Format

Input

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

Output

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

Sample 1

Input

ababa

Output

5 3 1 4 2

Limitation

1s, 1024KiB for each test case.

Hint

1≤n≤106

Source

Vijos Original