G. Наибольший палиндром

Найдите наибольшую подстроку, являющуюся палиндромом. Если таких несколько, выведите ту, что начинается раньше.

Одна строка длины $n$ ($1 \le n \le 10^5$) из строчных латинских букв.

Наибольшая палиндромная подстрока.