Ngân hàng dùng loại mật khẩu sử dụng một lần cho mọi truy cập tới các dịch vụ của ngân hàng.

Khi có yêu cầu truy nhập ngân hàng sẽ cung cấp một từ khóa. Người truy nhập chỉ phải nhập vào mật khẩu là một xâu ký tự palindrome độ dài dài nhất nhận được khi xóa bớt một vài ký tự trong từ khóa đã cho.

Với từ khóa đã cho hãy xác định mật khẩu cần nhập vào. Nếu tồn tại nhiều xâu khác nhau cùng thỏa mãn yêu cầu thì đưa ra xâu bất kỳ.

Input

• Gồm một dòng chứa từ khóa ~S\ (|S| \le 10^3)~ và chỉ bao gồm các ký tự la tinh thường.

Output

• In ra mật khẩu tìm được.

Scoring

• Subtask 1: 30% số điểm có ~|S| \le 16~.

• Subtask 2: 30% số điểm có ~|S| \le 100~.

• Subtask 3: 40% số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

abgeba

Sample Output 1

abgba

Sample Input 2

aaaa

Sample Output 2

aaaa