B - パスワード Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

　メールにはプログラミングコンテストへの参加チケットと，圧縮ファイルが添付されていた．参加するには添付ファイルに含まれるパズルを解く必要があるようだ．しかし，圧縮ファイルにはパスワードが掛かっていた．しかも，正しいパスワードを入力しないと自動で消滅する仕組みだ！ファイルの消滅は，参加資格の剥奪を示す．招待しておきながら参加者を篩に掛ける気なのか．意外と厄介だぞ…

　メール本文には招待状の後に，アルファベットからなる複数の文字列が羅列してあった．どうやら，2つ以上の文字列を任意の順番でつなげてできた文字列のうち，辞書順最小となるものが添付ファイルのパスワードのようだ．

問題文

　文字列が N 個与えられる．N 個の文字列の中から 2 つ以上を選んで，任意の順番で繋げてできる文字列のうち，辞書順で最小なものを出力せよ．

　ここで文字列 A が文字列 B より辞書順で小さいとは，A と B を最初の文字から比べていったとき，異なる最初の文字がアルファベット順で小さいか，または A が B の接頭辞である (B = A + ... という形になっている) ことを言う．例えば， abcd は abdc より辞書順で小さく，abcd は abcdef より辞書順で小さい．

入力

入力は以下の形式で標準入力から与えられる． 
N
S_{1}
S_{2}
...
S_{i}
...
S_{N}
  • 1 行目には文字列の数 N(2 ≦ N ≦ 50) が与えられる．
  • 2 行目～ N+1 行目にはアルファベットの小文字のみを含む文字列が与えられる．
  • 各文字列の長さは 50 を超えない．

出力

与えられた文字列の中から 2 つ以上を選んで，任意の順番で繋げてできる文字列のうち，辞書順で最小なものを標準出力に 1 行で出力せよ．

入力例 1

2
abcd
efgh

出力例 1

abcdefgh
  • この場合，abcdefgh とefghabcd の 2 種類の文字列を作ることができる．abcdefgh の方が辞書順で前に来るため，ここは abcdefgh を出力する．

入力例 2

3
caa
abb
ab

出力例 2

ababb
  • 全部で 12 種類の文字列を作成でき，その中で最も辞書順で小さいのは ababb である．

Source Name

WUPC 2012