준회문

티몬과 품바가 새로운 놀이를 생각해냈다. 이번에는 특별한 종류의 문자열을 모으기로 했다. 다른 사람들이 이미 만든 문자열에는 싫증이 나서, 그들은 준회문을 만들어냈다.

문자열 $X[1..n]$은 다음 조건을 모두 만족하면 준회문이다.

• 길이가 1 이하인 문자열은 모두 준회문이다.
• $X[1..\lfloor n/2 \rfloor]$은 준회문이다.
• $X[n-\lfloor n/2 \rfloor..n]$은 준회문이다.
• $X_1 = X[1..\lceil n/2 \rceil]$, $X_2 = X^R[1..\lceil n/2 \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$)이 주어진다. 둘째 줄에는 길이가 $n$이고 소문자 영어 알파벳으로만 이루어진 문자열 $S$가 주어진다.

$S$의 부분 문자열 중 준회문이면서 길이가 가장 긴 것 $T$를 첫 줄에 출력한다. 그런 부분 문자열이 여러 개라면 그중 아무것이나 출력해도 된다.