001.#include<stdio.h>
002.#include<string.h>
003. 
004.#define LCONF (1<<18)+4
005.#define INF 2000000000
006.#define minim(a,b) (a<b ? a : b)
007. 
008.int n,sol;
009.int d[LCONF][20];
010.int pred[LCONF][20];
011.int nr[20],c[20][20];
012.char s[20][30005];
013.int pi[30005],v[20];
014. 
015.int kmp(int i1,int i2)
016.{
017.    int i,q=0;
018.     
019.    memset(pi,0,sizeof(pi));
020.     
021.    for(i=2;i<=nr[i2];i++)
022.    {
023.        while(q>0 && s[i2][q+1]!=s[i2][i])
024.            q=pi[q];
025.        if(s[i2][q+1]==s[i2][i])
026.            q++;
027.        pi[i]=q;
028.    }
029.     
030.    q=0;
031.    for(i=1;i<=nr[i1];i++)
032.    {
033.        while(q>0 && s[i1][i]!=s[i2][q+1])
034.            q=pi[q];
035.        if(s[i1][i]==s[i2][q+1])
036.            q++;
037.        if(q==nr[i2])
038.            return nr[i2];
039.    }
040.    return q;
041.}
042. 
043.// functia de aflare a costului cu KMP
044. 
045.void recur(int cf,int last)
046.{
047.    if(!cf)
048.        return ;
049.    v[++nr[0]]=last;
050.    recur(cf-(1<<(last-1)),pred[cf][last]);
051.}
052. 
053.// functia de reconstituire
054. 
055.int main ()
056.{
057.    int i,j,t,cf,aj=0,cff=0;
058.    freopen("adn.in","r",stdin);
059.    freopen("adn.out","w",stdout);
060.    scanf("%d\n",&n);
061.    for(i=1;i<=n;i++)
062.    {
063.        fgets(s[i]+1,sizeof(s[i])-1,stdin);
064.        nr[i]=strlen(s[i]+1);
065.        while(s[i][nr[i]]!='A'
066.        &&    s[i][nr[i]]!='C'
067.        &&    s[i][nr[i]]!='G'
068.        &&    s[i][nr[i]]!='T')
069.            nr[i]--;
070.    }
071.     
072.    // citirea
073.     
074.    for(i=1;i<=n;i++)
075.        for(j=1;j<=n;j++)
076.        {
077.            if(i==j)
078.                continue;
079.            c[i][j]=kmp(i,j);
080.            if(c[i][j]==nr[j] && (!(aj&(1<<(j-1)))))
081.                aj+=(1<<(j-1));
082.        }
083.                 
084.    // calcularea costurilor
085.     
086.    for(i=1;i<(1<<n);i++)
087.    {
088.        if(i&aj)
089.            continue;
090.        for(j=1;j<=n;j++)
091.        {
092.            if(!((1<<(j-1))&i))
093.                continue;
094.            cf=i-(1<<(j-1));
095.            if(!cf)
096.            {
097.                d[i][j]=nr[j];
098.                continue;
099.            }
100.            d[i][j]=INF;
101.            for(t=1;t<=n;t++)
102.            {
103.                if(!((1<<(t-1))&cf))
104.                    continue;
105.                if(d[cf][t]+nr[j]-c[t][j]<d[i][j])
106.                {
107.                    d[i][j]=d[cf][t]+nr[j]-c[t][j];
108.                    pred[i][j]=t;
109.                }    //if
110.            }   //for
111.        } //for
112.    }
113.    // ciclu hamiltonian
114. 
115.    cff=(1<<n)-1-aj;
116.    sol=INF;
117.    for(i=1;i<=n;i++)
118.        if(cff&(1<<(i-1)))
119.            sol=minim(sol,d[cff][i]);
120.    for(i=1;i<=n;i++)
121.        if(d[cff][i]==sol)
122.        {
123.            recur(cff,i);
124.            break;
125.        }
126. 
127.    // apelarea reconstituirii
128.     
129.    for(i=nr[0];i>=1;i--)
130.        for(j=c[v[i+1]][v[i]]+1;j<=nr[v[i]];j++)
131.            printf("%c",s[v[i]][j]);
132.    printf("\n");
133. 
134.    // afisarea
135.    return 0;
136.}