问题文

给定一个长度为 $N$ 的字符串 $S$。对于每个 $i$ ($1≦i≦N$)，定义 $S$ 的第 $i$ 个字符到第 $N$ 个字符之间的子字符串为 $S_i$。

请找出将 $S_1$，$S_2$，$...$，$S_N$ 按照任意顺序连接起来得到的字符串中，字典序最小的串。

约束条件

• $1≦N≦10^5$
• 字符串 $S$ 的长度等于 $N$
• 字符串 $S$ 仅包含小写英文字母

输入

从标准输入读入输入数据。

$N$

$S$

输出

输出 $N$ 行。第 $i$ 行输出 $p_i$。

其中，$(p_1，p_2，...，p_N)$ 是 $1$ 到 $N$ 的一个排列，满足以下条件：

• 将 $S_{p_1}$，$S_{p_2}$，$...$，$S_{p_N}$ 按照这个顺序连接起来得到的字符串是字典序最小的。

如果存在多个合法的答案，输出其中任意一个。

示例1

输入示例1

3
arc

输出示例1

1
3
2

将 arc、c、rc 按照这个顺序连接起来得到的 arccrc 是字典序最小的。

示例2

输入示例2

2
zz

输出示例2

1
2

也可以输出 $2$，$1$。

示例3

输入示例3

5
abaab

输出示例3

3
1
4
2
5