問題文

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