2018年10月，MIT建立了最新的纳米科技研究中心MIT.nano。此后，不断有新的研究成果在此产生。

有一天，研究者发现了一种新的生物，这种生物的基因中含有$n$条DNA序列，每一条都有一定的长度，科学家们可以将每条DNA序列切断，从而取出它的一个非空前缀。此后，他们可以将这些前缀按任意顺序连结起来形成一条完整的DNA序列，这样的DNA序列对治疗癌症有很大的作用。

每条DNA序列都仅包含大写字母“A”，“C”,“G”，“T”。

科学家们很快发现，DNA序列的字典序越小，则治疗癌症的效果越好，他们想知道给定$n$条DNA序列，他们能获得的字典序最小的DNA序列是什么。

输入格式

第一行一个正整数$n$，表示DNA序列的个数。

接下来$n$行，每行一个非空字符串表示一条DNA，保证每个字符均为“A”，“C”，“G”，“T”中的一个。

输出格式

输出一行一个字符串，表示能获得的字典序最小的DNA序列。

样例一

input

5
AGT
GTA
ATC
GGGGG
CAT

output

AACAGG

explanation

五条DNA序列分别取前缀“A”，“G”，“A”，“G”，“CA”，按照“A+A+CA+G+G”的顺序拼接起来即可获得答案。

样例二

见样例数据下载，满足存在一种最优解是按照1到$n$的顺序。

限制与约定

设$m$为所有字符串长度的最大值。

对于 $10\mathrm{\%}$ 的数据，$m=1$。

对于 $30\mathrm{\%}$ 的数据，$n,m\le 7$。

对于另外 $30\mathrm{\%}$ 的数据，满足存在一种最优解是按照1到$n$的顺序。

对于 $100\mathrm{\%}$ 的数据，$1\le n,m\le 50$。

时间限制2s，空间限制2G。

题解

https://matthew99.blog.uoj.ac/blog/5352