Princess, a Cryptanalyst

Time Limit : 8 sec, Memory Limit : 65536 KB

Princess, a Cryptanalyst

お姫様の暗号解読

English text is not available in this practice contest.

ある貧乏な国のおてんばで勇敢なお姫様は,お忍びで出かけた町である日本語で書かれた古文書を手に入れた.お姫様は日本語ができるため,さっそくこの古文書を読んでみた.すると,驚くべき事が分かった.この古文書は,古の秘宝の在処を示していたのである.ところが,秘宝の在処は暗号になっており,容易には分からないようになっていた.そこでお姫様は,従者であるあなたに暗号の解読を手伝うように命令を下した.

あなたはお姫様を助けるため昼夜を問わず調査を行った.その結果,Shortest Secret String (SSS) と呼ばれる文字列が解読に重要な役割を果たすことがわかった.ここで SSS とは,N 個の単語全部を部分文字列として含み,なおかつその長さが最小であるような文字列である.

あなたの仕事は,N 個の単語から SSS を見つけ出す事である.

Input

入力は複数のデータセットで与えられる.データセットの初めの一行は,データセットに含まれる単語の数N(1≦N≦10)が与えられる.続くN行に単語が与えられる.最後のデータセットの後に,0のみを含む一行が与えられる.

なお,入力で与えられる単語はアルファベット小文字のみからなり,長さは高々10であることが保証されている.

Output

各データセットについてSSS を一行に出力せよ.また,複数ある場合は辞書式順序で最小のものを出力せよ.

Sample Input

4
apple
length
things
thin
2
icp
cpc
3
zeta
eta
alphabet
2
until
till
0

Output for the Sample Input

applengthings
icpc
zetalphabet
untill

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2008, 2008
http://acm-icpc.aitea.net/