問題文
长度 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} 得到的字符串按字典顺序是最小的。 如果有多个
(p_1,p_2,...,p_N) ,则可以输出任意一个。 按
入力例1
3 arc
出力例1
1 3 2
arc,c,rc 顺序串联而成 arccrc 按字典顺序是最小的。
入力例2
2 zz
出力例2
1 2
此外, 您可以按2,1 的顺序输出它们。
入力例3
5 abaab
出力例3
3 1 4 2 5