Xâu con đối xứng dài nhất

Xâu đối xứng (palindrome) là xâu đọc ngược lại vẫn được chính nó. Cho xâu \(s\) gồm các chữ cái thường, hãy tìm xâu con đối xứng dài nhất của \(s\) (xâu con nhận được bằng cách xoá bớt một số ký tự và giữ nguyên thứ tự các ký tự còn lại).

Nếu có nhiều xâu con đối xứng cùng độ dài lớn nhất, in ra xâu nhỏ nhất theo thứ tự từ điển.

Input

Một dòng duy nhất chứa xâu \(s\).

Output

In ra xâu con đối xứng dài nhất (nhỏ nhất theo thứ tự từ điển nếu có nhiều xâu).

Constraints

• \(1 \le |s| \le 2000\)
• \(s\) chỉ gồm chữ cái tiếng Anh viết thường.

Sample Input

qabxbzaq

Sample Output

qabxbaq

Explanation

Xoá ký tự z ta được qabxbaq có độ dài \(7\) và đối xứng. Không có xâu đối xứng nào dài hơn.