問題文

文字列 S が与えられます。S の Prefix Array を求めなさい。

ただし、Prefix Arrayとは、Suffix Array (リンク先は Wikipedia「接尾辞配列」) の定義における「接尾辞」を「接頭辞」に変更したものです。

(具体例は下記の入出力例 1 で確認できます。)

制約

• 1 ≦ |S| ≦ 100,000
• S は小文字アルファベットのみからなる。

入力例 1

chokudai

出力例 1

1
2
3
4
5
6
7
8

chokudai のすべての接尾辞を辞書順にソートすると、以下のようになります。

• c
• ch
• cho
• chok
• choku
• chokud
• chokuda
• chokudai