It is a tradition that at the festivities in the village of Juan Filloy [Argentine writer born in 1894, self-proclaimed world recordman of palindromicity, thanks to which today we know over 8,000 Spanish palindromes.], he spends one afternoon in the shooting galleries. When the owners know that he will visit them, instead of prizes in the ducks that have to be shooted, they place letters so that Juan can have fun shooting some ducks to form a palindrome with the letters in the surviving ducks (that is, the letters in the remaining ducks read the same both from left to right and from right to left). For example, if Juan faces the series of ducks in the figure below, he would shoot the ducks in positions 1, 4 and 6, thus forming the palindrome ROTATOR. In addition, Juan likes to brag in front of the gals who look at him expectantly, so he is not satisfied with just finding a palindrome but tries to do it by shooting as few ducks as possible. In case of a tie, Juan prefers to shoot ducks on the left, because on the right the sun blinds him. Would you know how to do the same? Input Input will consist of multiple test cases, each on one line. Each case consists of a series of a minimum of 1 and a maximum of 1,000 capital letters of the English alphabet, without special symbols or spaces. Output For each test case a line containing the longest palindrome that can be formed by removing (if necessary) some of the letters from the input will be written. In case of a tie, you must imitate John, eliminating letters on the left. Sample Input PROSTRATOR DELEVELED ARADAROSOSOMI OSORASODAR Sample Output ROTATOR DELEVELED OSOSO RADAR