A. Бернард и красивый палиндром
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бернарду подарили строку длины $$$N$$$, и он сразу же принялся её изучать.

Больше всего он любит искать в строке палиндромы, то есть такие подстроки, которые одинаково читаются слева направо и наоборот. Он быстро нашел все палиндромы и решил усложнить задачу. Бернард ввел термин «красивый палиндром». Красивым палиндромом он назвал строку, которая удовлетворяет следующим условиям:

  • Строка является палиндромом
  • Имеет четную длину
  • Обе половины строки являются палиндромами

Теперь Бернард хочет в подаренной ему строке найти самую длинную подстроку, являющуюся красивым палиндромом. Но эта задача оказалась достаточно сложной, поэтому он просит вас помочь ему.

Входные данные

Первая строка содержит целое число $$$N (2 \le N \le 5 \cdot 10^5)$$$ — длина строки.

Далее следует строка $$$S$$$ длины $$$N$$$, состоящая из строчных латинских букв.

Выходные данные

В первой строке выведите одно целое число — длину самого длинного красивого палиндрома.

Во второй строке выведите сам палиндром. Если подходящих ответов несколько, выведите любой.

Система оценки
ГруппаДоп. ограниченияБаллыТребуемые подзадачиТип проверки
$$$1$$$$$$N \leq 500$$$$$$20$$$—Полная
$$$2$$$$$$N \leq 5000$$$$$$40$$$$$$1$$$Полная
$$$3$$$—$$$40$$$$$$1,2$$$Полная
Примеры
Входные данные
7
abaabbc
Выходные данные
2
bb
Входные данные
6
abaaba
Выходные данные
6
abaaba
Входные данные
6
abadbc
Выходные данные
0
Примечание

В первом примере также подойдет строка «aa».