eolymp
bolt
Try our new interface for solving problems
Problems

Maximum palindrome

Maximum palindrome

Time limit 1 second
Memory limit 128 MiB

Remove from the given line the least number of characters to get a palindrome (the string that reads the same from right to left and from left to right).

Input data

Nonempty string of length no more than 100 symbols. The string contains only uppercase Latin letters.

Output data

Print the palindrome of maximum length that can be obtained from the given line by deleting some of its letters. If several solutions exist, print one (any) of them.

Examples

Input example #1
WQWQEWAEQ
Output example #1
QWEWQ