29215번 - Полупалиндромы 스페셜 저지다국어

Тимон и Пумба придумали себе очередное развлечение! В этот раз они надумали коллекционировать строки особого вида. Однако все уже придуманные другими строки им наскучили, потому они придумали полупалиндромы!

Полупалиндромом называется строка $X[1..n]$, удовлетворяющая следующим условиям:

• Любая строка длины не более 1 --- полупалиндром.
• Строка $X[1..\left \lfloor {\frac n2}\right \rfloor]$ является полупалиндромом.
• Строка $X[n-\left \lfloor {\frac n2}\right \rfloor ..n]$ является полупалиндромом.
• Обозначим $X_1 = X[1..\left \lceil {\frac n2}\right \rceil], X_2 = X^R[1..\left \lceil {\frac n2}\right \rceil]$. Будем говорить, что символ $X_1[i]$ соответствует символу $X_2[i]$. Тогда одинаковым символам из $X_1$ должны соответствовать одинаковые символы из $X_2$, и наоборот.

Строка $X[i..j]$ обозначает подстроку строки $X$ с индексами от $i$ до $j$ включительно. Строка $X^R$ обозначает развернутую строку $X$. $\lceil a\rceil$ означает число $a$, округленное вверх, $\lfloor a\rfloor$ --- число $a$, округленное вниз.

У Пумбы есть длинная строка $S$. Тимон хочет найти самую длинную подстроку $S$ так, чтобы она была полупалиндромом. Помогите ему!

В первой строке находится целое число $n$ --- длина строки ($1 \le n \le 3000$). Во второй строке содержится строка $S$, состоящая из $n$ строчных букв английского алфавита.

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