辞書順ソート R(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

N 個の文字列 S_1, ..., S_N が与えられます。これらの文字列をトライ木に格納した後、トライ木に格納された文字列を辞書順に出力してください。
辞書順とは、辞書に出てくる順番のことで、たとえば abc, aaa, acb, abd の 4 つを辞書順に並び替えると aaa, abc, abd, acb の順になります。

入力される値

N
S_1
...
S_N

・ 1 行目に文字列の数 N が与えられます。
・続く N 行に文字列 S_1, ..., S_N が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: i 行目には辞書順で i 番目の文字列を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて, 以下の条件をみたします

・1 ≦ N ≦ 10^4.
・Sはアルファベット小文字で構成された文字列
・1 ≦ |S_i| ≦ 100 (|S_i|は、S の文字数です。)
・S_i≠S_j (i≠j)

入力例1: 5
zzzzz
ab
aab
aa
a

出力例1: a
aa
aab
ab
zzzzz

入力例2: 4
d
c
b
a

出力例2: a
b
c
d

問題一覧へ戻る