Вернувшись к решению задач, Гильдонг взялся за изучение палиндромов. Он выяснил, что палиндром это строка, которая равна своему перевороту. Например, строки «pop», «noon», «x», и «kkkkkk» являются палиндромами, а строки «moon», «tv», и «abab» не являются. Пустая строка также является палиндромом.
Гильдонгу очень понравился этот концепт, так что он решил немного с ним поиграть. У него есть \(n\) различных строк равной длины \(m\). Он хочет удалить некоторые из этих строк (возможно, ни одну, или все) и переставить оставшиеся, чтобы их конкатенация была палиндромом. Он также хочет, чтобы палиндром был как можно длиннее. Помогите ему решить эту задачу!
Выходные данные
В первую строку выведите длину наибольшего палиндрома.
Во вторую строку выведите искомый палиндром. Если есть несколько возможных ответов, выведите любой. Если палиндром пуст, то можете как вывести пустую строку, так и не выводить эту строку вообще.
Примечание
В первом примере «battab» также является корректным ответом.
Во втором примере есть 4 разных возможных корректных ответа, включая ответ из примера. Мы не будем давать никаких подсказок, какими являются остальные ответы.
В третьем примере единственная возможная строка — пустая.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
tab
one
bat
|
6
tabbat
|
|
2
|
4 2
oo
ox
xo
xx
|
6
oxxxxo
|
|
3
|
3 5
hello
codef
orces
|
0
|
|
4
|
9 4
abab
baba
abcd
bcde
cdef
defg
wxyz
zyxw
ijji
|
20
ababwxyzijjizyxwbaba
|