Cho xâu ~S~.

Yêu cầu: Tìm của xâu con (liên tiếp) đối xứng dài nhất.

Input

Một dòng duy nhất chứa xâu kí tự ~S~ (~|S|\le 10^6~)

Output

In ra một xâu kí tự là xâu con đối xứng dài nhất của ~S~. Nếu có nhiều xâu như vậy thì in ra xâu xuất hiện đầu tiên

Sample Input

abacd

Sample Output

aba