Annettuna on merkkijono, ja tehtäväsi on etsiä pisin palindromi, joka on merkkijonon osajonona. Esimerkiksi merkkijonossa aybabtu pisin palindromi on bab.

Syöte

Syötteenä on merkkijono, jossa on n merkkiä ja jokainen merkki on väliltä a–z.

Tuloste

Tulosta merkkijonon pisin palindromi.

Jos ratkaisuja on useita, voit tulostaa niistä minkä tahansa.

Rajat

• 1 \le n \le 10^6

Esimerkki

Syöte:

aybabtu

Tuloste:

bab