给出一个长度为 $n$ 的由小写字母组成的字符串 $a$，设其中第 $i$ 个字符为 $a_i (1\le i\le n)$。
设删掉第 $i$ 个字符之后得到的字符串为 $s_i$，请按照字典序对 $s_1,s_2,\cdots,s_n$ 从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。
输入格式
第一行一个整数 $n$。
第二行一个长为 $n$ 的由小写字母组成的字符串 $a$。
输出格式
输出一行 $n$ 个整数 $k_1, k_2, \dots , k_n$，用空格隔开。表示 $s_{k_1}< s_{k_2} < \dots < s_{k_n}$。
样例数据
样例 1 输入
7 aabaaab
样例 1 输出
3 7 4 5 6 1 2
样例 1 解释
$$ \begin{align} s_1 = s_2 & = abaaab \nonumber \\ s_3 & = aaaaab \nonumber \\ s_4 = s_5 = s_6 & = aabaab \nonumber \\ s_7 & = aabaaa \nonumber \end{align} $$
子任务
对于所有数据，$1\le n\le 10^6$。
- 对于 $10\%$ 的数据，$1 \le n \le 2000$；
- 对于另外 $20\%$ 的数据，$1 \le n \le 10^5$ 且任意两个相邻字符 $a_i,a_{i+1}$ 不相等；
- 对于另外 $30\%$ 的数据，$1 \le n \le 10^5$；
- 对于余下 $40\%$ 的数据，无特殊限制。