Cho một xâu, nhiệm vụ của bạn là xác định xâu con palindrome dài nhất của xâu đó. Ví dụ, palindrome dài nhất trong aybabtu là bab.

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~. Mỗi ký tự là một trong các chữ a–z.

Kết quả

In ra palindrome dài nhất trong xâu. Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

aybabtu

Kết quả:

bab