Бернарду подарили строку длины $$$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».
