/* 
 * File:   main.cpp
 * Author: Tibor
 *
 * Created on December 21, 2011, 3:13 PM
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

/*
 * 
 */
int num = 0, levagasosszeg = 0, *eredmeny;
string *adn;
int **levag;
int *maxelotte;
int *maxmogotte;

bool foglalte(int n, int *elozmeny, int elem) {
    for (int i = 0; i < n; i++)
        if (elozmeny[i] == elem)return true;
    return false;
}

void keres(int n, int osszeg, int *elozmeny) {
    if (n >= num) {
        if (osszeg > levagasosszeg) {
            for (int i = 0; i < num; i++)
                eredmeny[i] = elozmeny[i];
            levagasosszeg = osszeg;
        }
    } else {
        for (int i = 0; i < num; i++)
            if (!foglalte(n, elozmeny, i)) {
                elozmeny[n] = i;
                if (n == 0)
                    keres(n + 1, osszeg, elozmeny);
                else
                    keres(n + 1, osszeg + levag[elozmeny[n - 1]][i], elozmeny);
            }
    }
}

void sejtkeres(int n, int osszeg, int *elozmeny) {
    if (n >= num) {
        if (osszeg > levagasosszeg) {
            for (int i = 0; i < num; i++)
                eredmeny[i] = elozmeny[i];
            levagasosszeg = osszeg;
        }
    } else {

        if (n == 0) {
            int x = 0;
            for (int i = 1; i < num; i++)
                if (maxelotte[x]> maxelotte[i])x = i;
            elozmeny[0] = x;
            keres(n + 1, osszeg, elozmeny);
        } else {
            int x = -1;
            for (int i = 0; i < num; i++)
                if (!foglalte(n, elozmeny, i)) {
                    if (x < 0)x = i;
                    if (levag[elozmeny[n - 1]][x] < levag[elozmeny[n - 1]][i])
                        x = i;
                }
            elozmeny[n] = x;
            keres(n + 1, osszeg + levag[elozmeny[n - 1]][x], elozmeny);
        }
    }
}
int leveg(string e, string m) {
    int max = e.size() < m.size() ? e.size() : m.size();
    int n = 0, ret = 0;
    
/** /
    n=max-1;
    while (n) {
        bool b = true;
        for (int i = 0; i <= n; i++) {
            if (e.at(e.size() - n + i - 1) != m.at(i)) {
                b = false;
                break;
            }
        }
        if (b)
            return n+1;
        n--;
    }
    //*/
    /**/
    //while (n < max) {
        bool b = true;
        for (int i = 0; i <= n; i++) {
            if (e.at(e.size() - n + i - 1) != m.at(i)) {
                b = false;
                break;
            }
        }

        n++;
        if (b)
            ret = n;
    //}//*/
    return ret;
}

int main(int argc, char** argv) {
    string line;
    ifstream myfilein("adn.in");
    if (myfilein.is_open()) {
        if (myfilein.good()) {
            getline(myfilein, line);
            //            cout << line.c_str() << endl;
            num = atoi(line.c_str());
        }
        adn = new string[num];
        for (int i = 0; i < num; i++)
            if (myfilein.good()) {
                getline(myfilein, line);
                //                cout << line.c_str() << endl;
                adn[i] = line;
            }
        myfilein.close();
    } //else cout << "Unable to open file";

    for (int i = 0; i < num; i++)
        for (int j = 0; j < num; j++) {
            if (j == i || adn[i].empty() || adn[j].empty()) continue;

            if (adn[i].find(adn[j]) < 50)
                adn[j] = "";
        }

    //    cout << endl;

    int n = 0;
    for (int i = 0; i < num; i++)
        if (!adn[i].empty())n++;
    string adn2[n];
    n = 0;
    for (int i = 0; i < num; i++)
        if (!adn[i].empty())adn2[n++] = adn[i];
    adn = adn2;
    num = n;

    levag = new int*[num];
    for (int i = 0; i < num; i++) {
        levag[i] = new int[num];
        for (int j = 0; j < num; j++) {
            levag[i][j] = i != j ? leveg(adn[i], adn[j]) : 0;
        }
    }
    maxelotte = new int [num];
    maxmogotte = new int [num];
    for (int i = 0; i < num; i++) {
        maxelotte[i] = 0;
        maxmogotte[i] = 0;
        for (int j = 0; j < num; j++) {
            if (maxelotte[i] < levag[j][i])
                maxelotte[i] = levag[j][i];
            if (maxmogotte[i] < levag[i][j])
                maxmogotte[i] = levag[i][j];
        }
    }
    //    cout << "\n------------\n";
    //    for (int i = 0; i < num; i++) {
    //        cout << endl;
    //        for (int j = 0; j < num; j++) {
    //            cout << levag[i][j] << " ";
    //        }
    //    }

    //    cout << endl;
    eredmeny = new int[num];
    sejtkeres(0, 0, new int[num]);
    //    keres(0, 0, new int[num]);
    //    for (int i = 0; i < num; i++)
    //        cout << " " << eredmeny[i];
    //    cout << endl << levagasosszeg;
    //    cout << endl;

    //    for (int i = 0; i < num; i++)
    //        cout << i << adn[i] << endl;

    ofstream myfile;
    myfile.open("adn.out");
    char *c = new char[1000];
    myfile << adn[eredmeny[0]];
//    for (int i = 1; i < num; i++) {
//        for (int j = 0; j < 1000; j++)c[j] = 0;
//        adn[eredmeny[i]].copy(c, adn[eredmeny[i]].size() - levag[eredmeny[i - 1]][eredmeny[i]], levag[eredmeny[i - 1]][eredmeny[i]]);
//        myfile << c;
//    }
    myfile.close();
    return 0;
}