#P18037. Cat Cut

Cat Cut

Cat Cut

题目描述

给定 NN 个长度均为 MM、只含小写英文字母的字符串 S1,…,SNS_1,\ldots,S_N。

初始时令 X=S1X=S_1,然后依次进行 N−1N-1 次操作。第 ii 次操作先把 XX 与 Si+1S_{i+1} 按此顺序拼接,得到长度为 2M2M 的字符串 YY;再任选 YY 的一个长度为 MM 的连续子串,将 XX 替换为这个子串。

求操作结束后,XX 可能达到的字典序最小值。

输入格式

第一行两个整数 N,MN,M。

接下来 NN 行,每行一个长度为 MM 的字符串 SiS_i。

2≤N≤20002\le N\le2000,1≤M≤20001\le M\le2000;字符串仅含小写英文字母。

输出格式

输出字典序最小的最终字符串。

样例 1

输入:

2 3
cat
cut

输出:

atc

样例 2

输入:

2 1
a
b

输出:

a

样例 3

输入:

3 8
jastaway
tatesoto
soryuusi

输出:

asoryuus