Problem A : Palindromic Subsequence

Time Limit: 3 sec

A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.

Constraints

Maximum length of string is 1000.
Each string has characters 'a' to 'z' only.

Input Format

Input consists of several strings, each in a separate line. Input is terminated by EOF.

Output Format

For each line in the input, print the output in a single line.

Sample Input

aabbaabb
computer
abzla
samhita

Sample Output

aabbaa
c
aba
aha

Problem Setters: Vijay S, Rajesh S R

Written for Samhita' 08