Problem: Given a string s, determine if it contains any palindrome of length exactly 100 as a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of s and is as long as possible.

Input

The only line of the input contains one string s of length n (1 ≤ n ≤ 5·104) containing only lowercase English letters.

Output

If s contains a palindrome of length exactly 100 as a subsequence, print any palindrome of length 100 which is a subsequence of s. If s doesn't contain any palindromes of length exactly 100, print a palindrome that is a subsequence of s and is as long as possible.

If there exists multiple answers, you are allowed to print any of them.

Examples

Input

bbbabcbbb


Output

bbbcbbb


Input

rquwmzexectvnbanemsmdufrg


Output

rumenanemur

Note

A subsequence of a string is a string that can be derived from it by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward or backward.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Palindrome {
     static int n = 0;
     static char [] c;
     static int [][] memo;
     static int [][] taken;
    public static void main(String[] args) throws IOException {
        BufferedReader rdr = new BufferedReader (new InputStreamReader(System.in));
         c = rdr.readLine().toCharArray();
         n = c.length;
         if(n >= 2600) {
             int [] store = new int [26];
             for(int i = 0; i < n; i++) 
                 store[c[i] - 'a']++;
             for(int i = 0; i < 26;i++)
                 if(store[i] >= 100) {
                     for(int j = 0; j < 100; j++)
                         System.out.print(((char)('a'+i)));
                     return;
                 }
         }
         memo = new int [n + 1][n + 1];
         taken = new int [n + 1][n + 1];
         for(int i = 0; i < n+1; i++)
             Arrays.fill(memo[i], -1);
         dp(0,n-1);
         int counter = 0;
         boolean [] with = new boolean [n + 1];
         int j = n - 1; int i = 0;
         while(i < j && counter < 100) {
                 if(taken[i][j] == 1) {
                     with[i++] = with[j--] = true; counter +=2;
                 }
                 else if(taken[i][j] == 2) {
                     i++;
                 }
                 else j--;
         }
         if(i == j && counter < 100)
             with[i] = true;
         for(int k = 0;k < n;k++) if(with[k])
             System.out.print(c[k]);
    }
    public static int dp (int lo , int hi) {
        if(lo > hi) return 0;
        if(lo == hi) return memo[lo][hi] = 1;
        if(memo[lo][hi] != -1) return memo[lo][hi];
        if(c[lo] == c[hi]) {
            taken[lo][hi] = 1;
            return memo[lo][hi] = 2 + dp(lo + 1, hi - 1);
        }
        int first = dp(lo + 1 , hi);
        int second = dp(lo , hi - 1);
            if(first > second) {
                taken[lo][hi] = 2;
                return memo[lo][hi] = first;
            }
            else {
                taken[lo][hi] = 3;
                return memo[lo][hi] = second;
            }
    }
}