Tehtäväsi on etsiä pisin palindromi, joka on annetun merkkijonon osana. Esimerkiksi merkkijonon aybabtu pisin palindromi on bab.

Syöte

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

Tuloste

Tulosta pisin merkkijonossa esiintyvä palindromi. Jos ratkaisuja on useita, voit tulostaa minkä tahansa niistä.

Rajat

• 1 \le n \le 10^6

Esimerkki

Syöte:

aybabtu

Tuloste:

bab