Palindrome

A palindrome is a sequence of characters that reads the same forwards and backwards.

Your task is to determine the longest palindrome P that can be formed from a given string S by removing any number of characters (including none).

Input

The input consists of a single string S, composed of lowercase Latin letters. The length of S will not exceed 1000 characters.

Output

The output should be the longest palindrome you can obtain. If there are multiple palindromes of the same maximum length, you may output any one of them.

Examples