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.*;
import java.lang.Math;
public class B335{
    public static String s;
    public static int[][] res= new int[103][50020];
    public static void track(int d,int x){
	System.out.print(s.charAt(x));
	if (d>2)
	    for(int i=x+1;i<res[d][x];i++)
		if (res[d-2][i]<res[d][x]){
		    track(d-2,i);
		    break;
		}
	if (d!=1)System.out.print(s.charAt(x));
    }
    public static void main(String[] agrs){    
	Scanner f= new Scanner(System.in);
	s=f.nextLine();
	int[][] l= new int[50020][30];
	int[][] r= new int[50020][30];
	int[][] list= new int[30][50020];
	int[] cn= new int[30];
	int inf=s.length()+10;
	int ans=0;
	int x=0;
	for(int i=0;i<=25;i++)cn[i]=0;
	for(int i=0;i<s.length();i++)list[s.charAt(i)-'a'][++cn[s.charAt(i)-'a']]=i;
	for(int i=0;i<=25;i++){
	    list[i][cn[i]+1]=inf;
	    list[i][0]=-inf;
	}

	for(int i=s.length()-1;i>=0;i--)
	    for(int j=0;j<=25;j++){
		while (cn[j]>0 && list[j][cn[j]]>i)cn[j]--;
		r[i][j]=list[j][cn[j]+1];
	    }
	for(int i=0;i<s.length();i++)
	    for(int j=0;j<=25;j++){
		while (list[j][cn[j]]<i)cn[j]++;
		l[i][j]=list[j][cn[j]-1];
	    }
	for(int d=0;d<=100;d++)
	    for(int i=0;i<s.length();i++)res[d][i]=inf;
	for(int i=0;i<s.length();i++){
	    res[1][i]=i;
	    res[2][i]=r[i][s.charAt(i)-'a'];
	}
       
	for(int d=1;d<=100;d++){
	    int m=inf;
	    for(int i=s.length()-1;i>=0;i--){
		if (m!=inf)res[d+2][i]=Math.min(res[d+2][i],r[m][s.charAt(i)-'a']);
		if (res[d][i]!=inf){
		    ans=d;
		    x=i;
		    m=Math.min(m,res[d][i]);
		}
		}
				
	}
	track(ans,x);
    }	 					    
}