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.util.Scanner;
public class palindrome
{
    static String ans="";
    static Integer dp[][];
    static String s;
    public static void main(String[] args) throws Exception
    {
        Scanner in = new Scanner(System.in);
        int[] freq = new int[26];
        s = in.nextLine();
        for(int i = 0; i < s.length(); i++)
        {
        	if(++freq[s.charAt(i)-97]>=100) {
        		for(int j = 0; j < 100; j++) 
        			System.out.print(s.charAt(i));  
        		return;
        	}
        }        
        dp = new Integer[s.length()][s.length()];
        int lb = 0; int ub = s.length()-1;
        while(true)
        {         	
        	if(lb>ub) {
        		System.out.println(ans+new StringBuffer(ans).reverse().toString());
        		return;
        	}
        	if(lb==ub ||ans.length()>=50)
        	{
        		String t = (ans.length()<50)?""+s.charAt(lb):"";
        		System.out.println(ans+t+new StringBuffer(ans).reverse().toString());
        		return;
        	}
        	if(s.charAt(lb)==s.charAt(ub))
        	{
        		ans+=s.charAt(lb);lb++; ub--;
        	}
        	else if (solve(lb+1,ub)==solve(lb,ub))
        		lb++;
        	else
        		ub--;
        }
    }
    public static int solve(int lb, int ub) 
    {
        if(dp[lb][ub]!=null)
            return dp[lb][ub]; 
        if(lb>ub)
            return 0;
        if(lb==ub)
            return dp[lb][ub]=1;
        if(s.charAt(lb)==s.charAt(ub))       
            return dp[lb][ub]=2+solve(lb+1,ub-1);
        else
            return dp[lb][ub]=Math.max(solve(lb+1,ub),solve(lb,ub-1)); 
    }
}