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

Input

• Dòng đầu vào duy nhất chứa một chuỗi độ dài \(n\). Mỗi kí tự là một trong những a - z.

Output

• In xâu đối xứng dài nhất trong xâu. Nếu có một số đáp án, bạn có thể in bất kỳ đáp án nào trong số đó.

Constraints

• \(1 \leq n \leq 10^6\)

Example

aybabtu

bab