Problem:


 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



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


Sample output:
applengthings
icpc
zetalphabet
untill

Submission status: Wrong Answer

Solution code:
def checkwordkaburi(word1,word2):
    for h in range(len(word1)): #headletter
        kaburilength=min(len(word1)-h,len(word2))
        if word1[h:h+kaburilength]==word2[:kaburilength]:
            return kaburilength
    return 0

def connectword(word1,word2,kaburi):
    if kaburi<len(word2):
        return word1+word2[kaburi:]
    else:
        return word1

while(1):
    N=int(raw_input())
    if N==0:
        break
    else:
        wordid=[]
        points=[[0 for y in range(N)] for x in range(N)]
        for i in range(N):
            wordid.append(raw_input())
        wordid.sort()
        for i in range(N): #points initializing
            word1=wordid[i]
            for j in range(N):
                word2=wordid[j]
                if i==j:
                    points[i][j]=-1
                else:
                    points[i][j]=checkwordkaburi(word1,word2)
        while N>1:
            largestk=-1
            largestkset=(0,0)
            for i in range(N):
                for j in range(N):
                    if points[i][j]>largestk:
                        largestk=points[i][j]
                        largestkset=(i,j)
            [I,J]=largestkset
            word2=wordid[J]
            word1=wordid[I]
            wordid[I]=connectword(word1,word2,largestk)
            for i in range(N):
                del points[i][J]
            del points[J]
            del wordid[J]
            if I>J:
                I=I-1
            N=N-1
            word1=wordid[I]
            for i in range(N):
                word2=wordid[i]
                if i==I:
                    points[i][i]=-1
                else:
                    points[I][i]=checkwordkaburi(word1,word2)
                    points[i][I]=checkwordkaburi(word2,word1)
        print wordid[0]