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 Input consists of several strings, each in a separate line. Input is terminated by EOF. Output 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