Longest Palindrome

Interview

Time limit1sMemory limit256 MB

Summary

Pick some of the distinct equal-length strings and order them so the concatenation is the longest possible palindrome, then print one such palindrome.

Level: Medium4 of 10
Topics: Hash map, Greedy, String
Solved: No attempts yet

Problem

Gildong is back to problem solving, and now he is studying palindromes. A palindrome is a string that is the same as its reverse. For example, "pop", "noon", "x", and "kkkkkk" are palindromes, while "moon", "tv", and "abab" are not. An empty string is also a palindrome.

Gildong has $n$ distinct strings, each of length $m$ . He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that their concatenation is a palindrome. He wants the palindrome to be as long as possible. Find one such palindrome.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 100$ , $1 \le m \le 50$ ), the number of strings and the length of each string.

The next $n$ lines each contain one string of length $m$ , consisting of lowercase Latin letters only. All strings are distinct.

Output

On the first line, print the length of the longest palindrome you made.

On the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or omit this line.

Hint

In the first example, "battab" is also a valid answer.

In the second example, there are 4 different valid answers, including the sample output. The other answers are not listed here.

In the third example, the empty string is the only valid palindrome.

Examples4

Example 1
Input
```
3 3
tab
one
bat
```
Expected output
```
6
tabbat
```
Example 2
Input
```
4 2
oo
ox
xo
xx
```
Expected output
```
6
oxxxxo
```
Example 3
Input
```
3 5
hello
codef
orces
```
Expected output
```
0
```

Example 4

Input

9 4
abab
baba
abcd
bcde
cdef
defg
wxyz
zyxw
ijji

Expected output

20
ababwxyzijjizyxwbaba