No.205 マージして辞書順最小

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 123
作問者 : EmKjpEmKjp
3 ProblemId : 412 / 出題時の順位表

問題文

N 個の文字列 $S_1, ..., S_N$ が与えられる。 これらの文字列を以下のような手順でマージして、1つの文字列にする。

  1. 文字列 $T$ を空文字列に初期化する。
  2. $S_1, ..., S_N$ から空文字列ではない文字列 $S_k$をどれかひとつ選ぶ、そのような文字列がない場合は 文字列 $T$ を結果として返して終了する。
  3. $S_k$ の最初の一文字を文字列 $T$の一番最後に追加する。
  4. $S_k$ から最初の一文字を削除する。
  5. 2. に戻る。
上記のマージで生成されうる文字列の中で、辞書順最小のものを答えよ。

入力

$N$
$S_1$
$S_2$
...
$S_N$

$1 \le N \le 50$
$1 \le |S_i| \le 50$ ($1 \le i \le N$)
文字列 $S_i$ は、アルファベット小文字('a'~'z')で構成される。

出力

マージで生成されうる文字列のうち辞書順最小のものを出力してください。最後に改行してください。

サンプル

サンプル1
入力
1
abc
出力
abc

1つしか文字列がないので、マージして得られるのは "abc" の1通りのみです。

サンプル2
入力
2
ac
bd
出力
abcd

生成されうる文字列は、"abcd", "abdc", "acbd", "bacd", "badc", "bdac" の6つで、その中で辞書順最小になるのは "abcd" になります。

サンプル3
入力
5
one
two
three
four
five
出力
ffioneothreeturvewo

サンプル4
入力
2
az
za
出力
azaz

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。