Wstęp do programowania w C++

Chera Man jest komiksowym bohaterem, podobnie jak Spiderman, Superman czy X-men, który walczy ze złymi palindromami odpowiedzialnymi za wszelkie zło ówczesnego świata. Żeby je pokonać, Chera Man musi znać ich nazwy. Do tej pory było to proste, ponieważ nasz bohater musiał tylko sprawdzić, czy podany ciąg jest palindromem. Niestety od jakiegoś czasu złe palindromy zaczęły się skutecznie kamuflować, co znacznie utrudniało zadanie. Kamuflaż polegał na tym, że palindrom był ukryty jako spójny podciąg pewnego ciągu. Czasami okazywało się, że ciąg był tak długi, że Chera Man nie mógł sobie z tym problemem poradzić sam. Dodatkowo w zadanym ciągu mogło znajdować się ukrytych wiele palindromów. Naszego bohatera interesował palindrom alfa - taki palindrom, który jest najdłuższy, a jeśli jest kilka o takiej samej długości, to ten, który pojawił się najwcześniej. Przyczyń się do uratowania świata i napisz program, który znajdzie palindrom alfę.

Wejście

Pewna niewielka liczba ciągów złożonych z małych liter języka łacińskiego. Długość ciągu nie przekracza 10⁶ znaków.

Wyjście

Dla każdego zestawu testowego wypisanie palindromu alfa.

Przykład

Wejście:
alamakota
bolekilolek

Wyjście:
ala
lol