百人一首

百人一首は日本の伝統的なゲームである． このゲームでは N 枚のカードが用いられ，それぞれのカードには1つの文字列が書かれている．細かいルールは省略するが， A君は N 枚のカードに書かれている文字列を何らかの順序でそれぞれちょうど1回ずつ読むことになった．

百人一首ではその接頭辞が非常に重要である．百人一首で使用される文字列として接頭辞は似ている言葉が多く， 連続して似たような文字列を読むとA君も混乱してしまう． そこでA君は，連続する二つのカードの文字列の接頭辞ができるだけ異なるように，カードを並べ替えようと考えた．

A君の目標は，「山札の読みやすさ」と呼ばれる指標を最小化するような山札を求めることである．ここで山札とは，この百人一首で読まれる N 枚のカードを並べ替えたものを指す．山札の読みやすさとは，山札内にある隣接したカードの類似度の総和を言う．2 枚のカードの類似度はそれらに書かれた文字列どうしの最長共通接頭辞の長さとして定義される．なお，文字列 t と u の最長共通接頭辞とは，t と u 両方の接頭辞であるような文字列のうち，最長のものを指す．

例えば，2 枚のカードに書かれた文字列がそれぞれ "jag" と "japan" であれば，これらのカードの類似度は 2 である．一方，"wan" と "nyan" であれば類似度は 0 である．

ところで，「山札の読みやすさ」が最小となる山札は複数存在するかもしれない．A君は，最小解としてありうる山札のうち，辞書順最小の山札を求めたい．ここで，山札 P と Q について P が辞書順で小さいとは，ある正の整数 i が存在して，1 番目から i-1 番目のカードまではそれぞれ同一のカードであり，かつ i 番目のカードの文字列は辞書順において山札 P のカードのほうが小さいことを言う．

あなたの仕事は，「山札の読みやすさ」を最小にするような山札の中で，辞書順最小となるものを求めることである．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

N
s₁
...
s_N

1行目にはカードの枚数を表す整数 N (1 ≤ N ≤ 100,000) が与えられる． 続く N 行にはカードに書かれた1文字以上の文字列が書かれてあり， 1行は英小文字のみで構成される．また，同一セット内において，各 s_i は互いに異なることが保証されている． さらに，s_i の長さの合計は 400,000 以下であることが保証されている．

入力の終わりは， 1つのゼロからなる行で示す．

Output

各データセットについて，「山札の読みやすさ」が最小となる山札の中で辞書順最小の山札の情報を，N 行に出力せよ．具体的には，そのような山札の i 番目のカードに書かれた文字列を，i 行目に出力することになる．

Sample Input

3
icpc
icfp
topcoder
4
apple
application
appointment
acmicpc
3
a
aa
aaa
4
a
aza
azb
b
0

Output for Sample Input

icfp
topcoder
icpc
apple
acmicpc
application
appointment
aa
a
aaa
a
aza
b
azb

辞書順の定義に注意すること．今回の定義では，文字列を連結した時に辞書順最小になるということを意味するわけではない．例えば，3番目の入力例では [aaa,a,aa] も「山札の読みやすさ」が最小となる解の一つであり，連結すれば同じ文字列になるため，辞書順最小の解に見えるかもしれない．しかしながら，今回の定義では先頭の文字列 "aa" と "aaa" が優先的に比較されるため，辞書順最小の解は [aa,a,aaa] となる．

---