AtCoder Regular Contest 050

D - Suffix Concat


Time limit時間制限 : 4sec / Memory limitメモリ制限 : 256MB

問題文

長さ N の文字列 S が与えられます。各 i (1≦i≦N) について、Si 文字目から N 文字目までの部分文字列を S_i と呼ぶことにします。

S_1S_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

arccrc の順番で連結して得られる arccrc が、辞書順で最小です。


入力例2

2
zz

出力例2

1
2

他には、21 の順番で出力してもよいです。


入力例3

5
abaab

出力例3

3
1
4
2
5

Submit提出する