Palindrome

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem C: Palindrome

Problem

太郎君はそれぞれの長さがLの文字列をN個持っている。太郎君は回文が大好きなので、N個のうちいくつかの文字列を選んで好きな順番に並べることで、できるだけ長い回文を作りたい。

太郎君が作ることのできる回文の中で、最長のものを求めよ。複数ある場合は、そのうち辞書順で最小のものを出力せよ。どのように選んで並べても回文が作れない場合は、空行を出力せよ。

Input

入力は以下の形式で与えられる。

N L
s1
s2
.
.
.
sN

1行目に、文字列の数Nと文字列の長さLが与えられる。続く2行目からN + 1行目に太郎君が持っている文字列s_iが与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N ≤ 1000
  • 1 ≤ L ≤ 30
  • s_iは英小文字からなる文字列である。

Output

最長の回文の中で辞書順最小のものを出力せよ。回文が作れない場合は空行を出力せよ。

Sample Input 1

4 2
oi
io
rr
rr

Sample Output 1

iorrrroi

Sample Input 2

5 1
a
b
c
a
c

Sample Output 2

acbca

Sample Input 3

3 3
uki
uku
uke

Sample Output 3

uku

Source: Aizu Competitive Programming Camp 2017 , Day 2, Aizu-Wakamatsu, Japan, 2017-09-19