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.io.PrintWriter;
import java.util.*;


public class B {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
	public void solve() throws IOException {				
		
		char[] s = reader.readLine().toCharArray();
		int len = s.length;
		
		int[] cnt = new int[26];
		for(int i = 0; i < s.length; i++){
			cnt[ s[i]-'a' ]++;
			if( cnt[ s[i]-'a' ] >= 100){
				for(int j = 0; j < 100; j ++)
					out.print( s[i] );
				out.println(); 
				return;
			}
		}
		
		int[][] dp = new int[len][len];
		int[][] way = new int[len][len];
//		int[][][] trace = new int[len][len][];
		for(int i = 0; i < len; i++){
			dp[i][i] = 1;
			way[i][i] = 0;
		}
		
//		for(int i = 0; i < len; i++)
//			for(int j = 0; j < len; j++)
//				trace[i][j] = new int[]{-1, -1};
		
		int al = -1;
		int ar = -1;
		
		outer: for(int cl = 2; cl <= len; cl++){
			for(int i = 0; i < len-cl+1; i++){
				int j = i+cl-1;
				if( s[i] == s[j] && cl == 2){
					dp[i][j] = 2;
					way[i][j] = 0;
				}
				else if(s[i] == s[j] ){
					dp[i][j] = dp[i+1][j-1] + 2;
//					trace[i][j] = new int[]{i+1,j-1};
					way[i][j] = 0;
					if( dp[i][j] == 100 || dp[i][j] == 101){
						al = i;
						ar = j;
						break outer;
					}
				}
				else{
					if( dp[i][j-1] > dp[i+1][j] ){
						dp[i][j] = dp[i][j-1];
//						trace[i][j] = new int[]{i, j-1};
						way[i][j] = 1;
					}
					else{
						dp[i][j] = dp[i+1][j];
//						trace[i][j] = new int[]{i+1, j};
						way[i][j] = 2;
					}
				}
			}
		}
				
		StringBuilder ans = new StringBuilder();
		int l=0, r=len-1;		
		if( al != -1){
			l = al;
			r = ar;
		}		
		int an_len = dp[l][r];
		
	    while(l<=r){
	    	if(way[l][r]==0){
	    		ans.append( s[l] );
	             l += 1;
	             r -= 1;
	         }
	         else if(way[l][r]==1)
	        	 r -= 1;
	         else if(way[l][r]==2)
	        	 l += 1;     
	    }
		
		String finalans = ans.toString();
		
		if( an_len % 2 == 0){
			finalans = finalans + ans.reverse().toString();			
		}
		else{
			finalans = finalans + ans.reverse().toString().substring(1);
			if( finalans.length() == 101){				
				finalans = finalans.substring(0, 50) + finalans.substring(51);
			}
		}
		
		for(int i = 0; i < finalans.length(); i++){
			if( finalans.charAt(i) != finalans.charAt(finalans.length()-1-i))
				throw new RuntimeException();
			if( finalans.length() > 100)
				throw new RuntimeException();
		}
		
//		out.println( dp[0][len-1] );
		out.println( finalans );
	}	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new B().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}