Chiều ngày 15/05, Tổng Giám đốc VNG Corp - Ông Lê Hồng Minh và Ông Lionel Yeo - Giám đốc điều hành khu vực Đông Nam Á của ST Telemedia Global Data Centres (STT GDC), đã công bố hợp tác xây dựng và vận hành các dự án trung tâm dữ liệu mới theo tiêu chuẩn quốc tế tại TP.HCM. Quan hệ đối tác này được kỳ vọng sẽ thúc đẩy quá trình chuyển đổi số tại Việt Nam.

Trong một buổi gặp gỡ, các nhà phát triển tại trung tâm dữ liệu mới nhận được một thử thách lập trình từ Ông Lionel Yeo. Ông yêu cầu các nhà phát triển giải một bài toán liên quan đến xâu ký tự và hoán vị palindrome. Nhiệm vụ của bạn là giúp các nhà phát triển giải bài toán này.

Cho một xâu ký tự (chỉ gồm các ký tự in thường trong bảng chữ cái tiếng anh), tìm hoán vị có giá trị lớn nhất, nếu có nhiều xâu có cùng giá trị lớn nhất thì in ra xâu có thứ tự từ điển nhỏ nhất.

Lưu ý: Giá trị của hoán vị được đính nghĩa là:

• Xét các xâu con liên tiếp của hoán vị là xâu Palindrome.
• Trong các xâu đó, giá trị của hoán vị chính là độ dài của xâu con dài nhất.

Input

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

Output

Xâu đáp án của đề bài.

Sample Input

baabac

Sample Output

aabcba

Note:

Giải thích: "aabcba" có xâu con palindrome dài nhất là "abcba" độ dài 5 cũng chính là đáp án tốt nhất mà chúng ta có thể tìm được.