Princess, a Cryptanalyst

Decryption of the princess

English text is not available in this practice contest.

A brave princess in a poor country's tomboy got an old document written in Japanese, a town she went out in stealth. The princess can speak Japanese, so I immediately read this old document. Then I found something amazing. This ancient document showed the whereabouts of the ancient treasure. However, the location of the treasure was encrypted, making it difficult to understand. So the princess ordered you, your servant, to help you break the code.

You conducted a day and night survey to help the princess. As a result, it was found that a character string called Shortest Secret String (SSS) plays an important role in cryptanalysis. Here, SSS is a character string that contains all N words as a substring and has the minimum length.

Your job is to find the SSS out of N words.

Input

Inputs are given in multiple datasets. The first line of the dataset is given the number of words N (1 ≤ N ≤ 10) contained in the dataset. Words are given in the following N lines. After the last dataset, a line containing only 0 is given.

It should be noted that the words given by input consist only of lowercase letters and are guaranteed to be at most 10 in length.

Output

Output the SSS on one line for each dataset. If there are more than one, output the smallest one in lexicographic order.

Sample Input


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


Output for the Sample Input


applengthings
icpc
zetalphabet
untill






Example

Input

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


Output

applengthings
icpc
zetalphabet
untill
#include<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<set>
#include<limits>
#include <complex>
using namespace std;


const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : num(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) { ; }
	Mod(int n) : num((n % mod + mod) % mod) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	assert(b.num != 0);
	return Mod(a) * inv(b);
}
Mod operator/=(Mod &a, const Mod b) {
	assert(b.num != 0);
	return a = a * inv(b);
}

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}


template<typename T>
vector<vector<T>> keisann(const vector<vector<T>>l, const vector<vector<T>>r) {
	vector<vector<T>>ans(l.size(), vector<T>(r[0].size()));
	assert(l[0].size() == r.size());
	for (unsigned int h = 0; h < l.size(); ++h) {
		for (unsigned int i = 0; i < r.size(); ++i) {
			for (unsigned int w = 0; w < r[0].size(); ++w) {

				ans[h][w] += l[h][i] * r[i][w];
			}
		}
	}
	return ans;
}
template<typename T>
vector<vector<T>>powgyou(vector<vector<T>>a, const long long int n) {
	assert(a.size() == a[0].size());
	if (!n) {
		vector<vector<T>>e(a.size(), vector<T>(a[0].size()));
		for (unsigned int i = 0; i < a.size(); ++i) {
			e[i][i] = 1;
		}
		return e;
	}
	if (n == 1)return a;
	else {
		vector<vector<T>>ans(a.size(), vector<T>(a[0].size(), 0));
		ans = powgyou(a, n / 2);
		ans = keisann(ans, ans);
		if (n % 2) {
			ans = keisann(ans, a);
		}
		return ans;
	}
}

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

const int INF = 2147483647;
const long long int L_INF = 9223372036854775807;

typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])

vector<pair<int, int>>uses;

//流量0の逆辺も張らないと正しく求まらないので注意
Weight maximumFlow(const Graph &ag, int s, int t) {

	Graph g(ag);
	for (int i = 0; i < ag.size(); ++i) {
		for (int j = 0; j < ag[i].size(); ++j) {
			int d = ag[i][j].dst;
			int s = ag[i][j].src;
			
			bool ok = false;
			for (int k = 0; k < ag[d].size(); ++k) {
				if (ag[d][k].src == s) {
					ok = true;
					break;
				}
			}
			if (!ok) {
				g[d].push_back(Edge(d, s, 0));
			}
		}
	}

	int n = g.size();
	Matrix flow(n, Array(n)), capacity(n, Array(n));
	REP(u, n) FOR(e, g[u]) capacity[e->src][e->dst] += e->weight;

	Weight total = 0;
	while (1) {
		queue<int> Q; Q.push(s);
		vector<int> prev(n, -1); prev[s] = s;
		while (!Q.empty() && prev[t] < 0) {
			int u = Q.front(); Q.pop();
			FOR(e, g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
				prev[e->dst] = u;
				Q.push(e->dst);
			}
		}
		if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
		Weight inc = INF;
		for (int j = t; prev[j] != j; j = prev[j])
			inc = min(inc, RESIDUE(prev[j], j));
		for (int j = t; prev[j] != j; j = prev[j])
			flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
		total += inc;
	}
}

map<long long int, int>soinnsuu(long long int a) {
	map<long long int, int>ans;
	for (long long i = 2; i*i <= a; ++i) {
		while (a%i == 0) {
			ans[i]++;
			a /= i;
		}
	}
	if (a != 1)ans[a]++;


	return ans;
}

bool isso(long long int a) {
	if (a == 1)return false;
	for (long long int i = 2; i*i <= a;++i) {
		if (!(a%i)) {
			return false;
		}
		else {
		}
	}
	return true;
}

struct vert {
	int deg;
	int s;
	int id;
	vert(int a, int b, int c) {
		deg = a;
		s = b;
		id = c;
	}
};



vector<vector<int>>kaburis;

vector<string>nsts;

pair<string,long long int> memo[1024][10];

pair<string,long long int> getans(bitset<10>bs,int fin) {
	if (memo[bs.to_ulong()][fin].second >= 0) {
		return {memo[bs.to_ulong()][fin]};
	}
	if (bs.count() == 0) {
		return memo[bs.to_ulong()][fin] = { "",0 };
	}
	else if (bs.count() == 1) {
		for (int i = 0; i < 10; ++i) {
			if (bs[i]) {
				return memo[bs.to_ulong()][fin] = { nsts[i], 0 };
			}
		}
	}
	long long int amax = -1;
	string ansst;
	for (int i = 0; i < 10; ++i) {
		if (i==fin) {
			bs[i] = false;
			for (int j = 0; j < 10; ++j) {
				if (bs[j]) {
					
					if (amax < getans(bs, j).second + kaburis[j][i]) {
						amax = max(amax, getans(bs, j).second + kaburis[j][i]);
						ansst = getans(bs, j).first + nsts[fin].substr(kaburis[j][i], nsts[fin].size() - kaburis[j][i]);
					}
					else if (amax == getans(bs, j).second + kaburis[j][i]) {
						amax = max(amax, getans(bs, j).second + kaburis[j][i]);
						ansst = min(ansst, getans(bs, j).first + nsts[fin].substr(kaburis[j][i], nsts[fin].size() - kaburis[j][i]));
					}
				}
			}
			bs[i] = true;
		}
	}
	return memo[bs.to_ulong()][fin] = { ansst,amax };
}

int main() {
	
	//int N; cin >> N;
	//vector<vector<int>>edges(N);
	//vector<vert>es;
	//for (int i = 0; i < N; ++i) {
	//	int degree, s; cin >> degree >> s;
	//	es.push_back(vert(degree,s,i));
	//}
	//vector<vert>sortes(es);
	////sort(sortes.begin(), sortes.end(), [](const vert&l, vert&r) {return l.deg < r.deg; });
	//for (int i = 0; i < sortes.size(); ++i) {
	//	if (sortes[i].deg == 1) {
	//		int  nowid(i);
	//		while (sortes[nowid].deg == 1) {
	//			sortes[nowid].deg--;
	//			edges[nowid].push_back(sortes[nowid].s);
	//			sortes[sortes[nowid].s].s ^= sortes[nowid].id;
	//			sortes[sortes[nowid].s].deg--;
	//			nowid = sortes[sortes[nowid].s].id;
	//		}
	//	}
	//}
	//int ans = 0;
	//for (int i = 0; i < N; ++i) {
	//	for (int j = 0; j < edges[i].size(); ++j) {
	//		ans++;
	//	}
	//}
	//cout << ans << endl;
	//for (int i = 0; i < N; ++i) {
	//	for (int j = 0; j < edges[i].size(); ++j) {
	//		cout << i << " " << edges[i][j] << endl;
	//	}
	//}

	/*int n; cin >> n;
	vector<int>sinsuus(n);
	for (int j = 0; j < 2; ++j) {


		vector<int>nums;
		for (int i = 0; i < n; ++i) {
			int a; cin >> a;
			nums.push_back(a);
		}


		for (int i = 0; i < n; ++i) {
			int pl = get(nums[i], nums[i]);
			update(nums[i], n, 1);
			sinsuus[i] += nums[i] - (pl);
		}
		int k;
		for (int i = 0; i < 2 * N; ++i) {
			seg[i] = NODE();
		}
	}
	for (int i = n- 1; i >= 0; --i) {
		if (sinsuus[i] >= n-i) {
			if(i!=0)
				sinsuus[i- 1]++;
			sinsuus[i] -= n-i;
		}
	}

	vector<int>ansnums(n);



	for (int i = 0; i < n; ++i) {
		ansnums[i] = sinsuus[i]+get(0,sinsuus[i]-1);
		update(sinsuus[i], sinsuus[i], 1);
	}
	
	return 0;*/

	//5:10
	while (1) {
		for (int i = 0; i < 1024; ++i) {
			for (int j = 0; j < 10; ++j) {
				memo[i][j] = { "",-1 };
			}
		}
		int n; cin >> n;
		if (!n)break;
		vector<string>sts;
		for (int i = 0; i < n; ++i) {
			string st; cin >> st;
			sts.push_back(st);
		}
		vector<bool>oks(n, true);
		
		for (int i = 0; i < sts.size(); ++i) {
			for (int j = 0; j < sts.size(); ++j) {
				if (i != j&&oks[i]&&oks[j]) {
					if (sts[i].find(sts[j])!=string::npos) {
						oks[j] = false;
					}
				}
			}
		}
		nsts.clear();
		for (int i = 0; i < n; ++i) {
			if (oks[i]) {
				nsts.push_back(sts[i]);
			}
		}

		kaburis.resize(nsts.size());
		for (int i = 0; i < nsts.size(); ++i) {
			kaburis[i].resize(nsts.size());
		}

		for (int i = 0; i < nsts.size(); ++i) {
			for (int j = 0; j < nsts.size(); ++j) {
				if (i != j) {
					int k = min(nsts[i].size(),nsts[j].size())-1;
					string a = nsts[i].substr(nsts[i].size() - k, k);
					string b = nsts[j].substr(0, k);
					while (nsts[i].substr(nsts[i].size() - k, k) != nsts[j].substr(0, k)) {
						k--;
					}
					kaburis[i][j] = k;
				}
			}
		}
		int kaburinum = -1;
		string ansst;
		for (int i = 0; i < nsts.size(); ++i) {
			if (kaburinum < getans(bitset<10>((1 << nsts.size()) - 1), i).second) {
				kaburinum = getans(bitset<10>((1 << nsts.size()) - 1), i).second;
				ansst = getans(bitset<10>((1 << nsts.size()) - 1), i).first;
			}else if (kaburinum == getans(bitset<10>((1 << nsts.size()) - 1), i).second) {
				ansst = min(ansst,getans(bitset<10>((1 << nsts.size()) - 1), i).first);
			}
		}
		cout << ansst << endl;
	}
	return 0;
}