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.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        String s = in.readLine();
        String rs = new StringBuilder(s).reverse().toString();
        if(s.length()<=2600) {
            int n = s.length();

            int[][]dp = new int[n+1][n+1];
            int[][] path = new int[n+1][n+1];

            for (int i = n-1; i > 0; i--) {
                dp[i][i] = 1;
                for (int j = i+1; j <= n; j++) {
                    if(s.charAt(i-1) == s.charAt(j-1)) {
                        dp[i][j] = dp[i+1][j-1] + 2;
                        path[i][j] = 2;
                    } else {
                        if(dp[i][j-1]>dp[i+1][j]) {
                            dp[i][j] = dp[i][j-1];
                            path[i][j] = -1;
                        }else{
                            dp[i][j] = dp[i+1][j];
                            path[i][j] = 1;
                        }

                    }
                }
            }
            int i = 1;
            int j = n;
            StringBuilder sb = new StringBuilder();
            char mid = 0;
            while(i<j) {
                if(path[i][j] == 2) {
                    char c = s.charAt(i - 1);
                    sb.append(c);
                    i++;j--;
                } else if(path[i][j] == 1) {
                    i++;
                } else {
                    j--;
                }
                
            }
            if(i==j) {
                mid = s.charAt(i - 1);
            }
            if(sb.length() >= 50) {
                sb = new StringBuilder(sb.substring(0,50));
                mid=0;
            }
            StringBuilder reverse = new StringBuilder(sb.toString()).reverse();
            if(mid != 0) {
                sb.append(mid);
            }
            sb.append(reverse);


            out.println(sb);
        } else {
            int[] a = new int[26];
            for (int i = 0; i < s.length(); i++) {
                a[s.charAt(i)-'a']++;
            }
            for (int i = 0; i < 26; i++) {
                if(a[i]>=100) {
                    char c = (char)('a'+i);
                    StringBuilder sb = new StringBuilder();
                    for (int j = 0; j < 100; j++) {
                        sb.append(c);
                    }
                    out.println(sb);
                    break;
                }
            }
        }
    }
}

class InputReader  extends BufferedReader {
    public InputReader(InputStream st) {
        super(new InputStreamReader(st));
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }


}