Grammy 有一个长度为 $n$ 的字符串 $S$，由小写英文字母组成。

对于一个字符串 $P$，从左到右读取它，将从未出现过的字母依次记为 $t_1, t_2, t_3, \dots, t_k$。例如，如果 $P = \text{“sesame”}$，我们记下 $\text{'s'}, \text{'e'}, \text{'a'}, \text{'m'}$。其最小表示 $R(P)$ 可以通过以下方式获得：将 $P$ 中所有出现的 $t_1$ 替换为字符集中的第一个字符（即 $\text{'a'}$），将 $P$ 中所有出现的 $t_2$ 替换为字符集中的第二个字符（即 $\text{'b'}$），以此类推。

例如，当字符集为小写英文字母时，$\text{“sesame”}$ 的最小表示是 $\text{“abacdb”}$，$\text{“edcca”}$ 的最小表示是 $\text{“abccd”}$，而 $R(\text{“xy”})$ 和 $R(\text{“zt”})$ 的最小表示均为 $\text{“ab”}$。

你的任务是根据最小表示对 $S$ 的所有后缀进行排序。形式化地，记后缀 $S_i S_{i+1} \dots S_{n-1} S_n$ 为 $S[i:]$。对于两个后缀 $S[i:]$ 和 $S[j:]$，如果 $R(S[i:])$ 在字典序上小于 $R(S[j:])$，则 $S[i:]$ 在目标顺序中必须排在 $S[j:]$ 之前。

请输出结果为一个下标数组 $sa$：$sa[i]$ 必须是目标顺序中第 $i$ 小的后缀的起始位置。形式化地，该数组必须满足： $$R(S[sa[1]:]) < R(S[sa[2]:]) < \dots < R(S[sa[n]:])$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)。 下一行包含一个长度为 $n$ 的字符串 $S$。保证 $S$ 仅由小写英文字母组成。

输出格式

输出 $n$ 个整数，表示答案。

样例

样例输入 1

6
aadead

样例输出 1

6 1 5 4 3 2