D - Suffix Concat Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

長さ 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