Suffix Sort

题号：NC240395
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

本题如果提交后显示“您的代码已保存查询超时，请重试”，则可以稍后在提交记录页面看到结果。

If you receive "您的代码已保存查询超时，请重试" after submitting, then you can see the result on the "submission status" page later.

Grammy has a string $S$ of length $n$ containing only lowercase letters.

For a string $s$ , if we record the first occurrence of each type of character in order as $t_1, t_2, t_3, \dots, t_k$ , then the minimal representation of $s$ can be obtained by replacing all occurrence of $t_1$ in $s$ by the first character of the character set (a), replacing all occurrence of $t_2$ in $s$ by the second character of the character set (b), and so on.

For example, when the character set is lowercase, the minimal representation of “edcca” is “abccd”, and “xy” and “zt” are essentially the same in terms of minimal representation.

Your task is sorting all suffixes of $S$ with a special regularity.

For two suffixes $S[i:]$ and $S[j:]$ , if the minimal representation of $S[i:]$ is less than
the minimal representation of $S[j:]$ in the lexicographic order, then $S[i:]$ is less than $S[j:]$ in the special regularity.

Please output the result array $sa[i]$ of the suffix sort with the special regularity. The $i$ -th element of $sa[i]$ is the position of the first character in the i-th smallest suffix of $S$ with the special regularity.

输入描述:

The first line contains one integers  ().

The next line contains a string  of length . It is guaranteed that  only consists of lowercase English alphabets.

输出描述:

Output  integers in a single line, representing the answer.

示例1

输入

复制

6
aadead

输出

复制

6 1 5 4 3 2