Palindrome cipher decryption

A secret society encrypts its messages with palindromes. A palindrome reads the same in both directions. MADAM, REVIVER and SUCCUS are palindromes, while ADAM, REVENGE and SOCCER are not. In this scheme a string of one or two letters does not count as a palindrome, so A and MM are not palindromes.

The encryption is simple. Extra letters are inserted into the original message so that the longest subsequence forming a palindrome is exactly the original message. To decrypt a message you extract its longest palindromic subsequence. A subsequence is the string you get by picking some letters out of a string and keeping the order of the letters you picked. For example, the longest palindromic subsequence of YMAOKDOAMIMHAADAMMA is MADAMIMADAM, of length 11.

You received several encrypted messages. Write a program that decrypts each one.

The input is a series of data sets, one encrypted message per line. Each message consists of capital letters A to Z only and is at most 2000 letters long. The number of lines is not given, and the input ends at end of file.

For every message the longest palindromic subsequence is longer than two letters.

For each message print the decrypted original on its own line.

If several palindromic subsequences reach the maximum length, print the one that comes first in lexicographic order. All candidates have the same length, so comparing them letter by letter from the left picks exactly one answer.