B Cat Cut

制限時間: 2 sec メモリ制限: 1024 MB

Cat Cut

Statement

\(N\) 個の長さ \(M\) の英小文字からなる文字列 \(S_1,\dots,S_N\) が与えられます。

はじめ \(X=S_1\) として以下の \(N-1\) 回の操作を行います。

\(i\) 回目の操作では \(X\) と \(S_{i+1}\) をこの順に連結してできた文字列を \(Y\) とし、 \(Y\) の長さ \(M\) の連続部分文字列を自由に選んで \(X\) をそれに置き換えます。

最終的な \(X\) としてあり得る辞書順最小の文字列を出力してください。

Input

\(1\) 行目に整数 \(N,M\) がこの順に与えられる。 ( \(2 \leq N \leq 2000, 1 \leq M \leq 2000\) )

続く \(N\) 行のうち \(i\) 行目に、長さ \(M\) の英小文字からなる文字列 \(S_i\) が与えられる。

部分点: \(2 \leq N \leq 50, 1 \leq M \leq 50\) を満たすケース全てに正答した場合、 \(1\) 点が与えられる。

Output

答えを出力せよ。

Examples

Input 1

2 3
cat
cut

Output 1

atc

Input 2

2 1
a
b

Output 2

Input 3

3 8
jastaway
tatesoto
soryuusi

Output 3

asoryuus

Note

入力例1では、はじめ \(X=\) catである。1回目の操作では \(Y=\) catcut となり、この内2番目から4番目までの連続部分文字列を選ぶと \(X=\) atc となってこれが辞書順最小である。