← 返回题目列表

AtCoder · arc050_d

D. 后缀连接

中文机器翻译题面 查看原题

問題文

长度 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