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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class B335 {

    static StringTokenizer st;
    static BufferedReader br;
    static PrintWriter pw;
    static int[][]p;
    static String s;
    static boolean f;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        s = next();
        int[]cnt = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i)-97]++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i] >= 100) {
                for (int j = 1; j <= 100; j++) {
                    pw.print((char)(i+97));
                }
                pw.close();
                return;
            }
        }
        int[][]dp = new int[n][n], dp2 = new int[n][n];
        p = new int[n][n];
        int[][]p2 = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= n-i; j++) {
                int left = j, right = j+i-1;
                if (dp[left+1][right-1] % 2==1) {
                    dp[left][right] = dp[left+1][right-1];
                    p[left][right] = 4;
                }
                if (dp[left][right-1] % 2==1 && dp[left][right-1] > dp[left][right]) {
                    dp[left][right] = dp[left][right-1];
                    p[left][right] = 3;
                }
                if (dp[left+1][right] % 2==1 && dp[left+1][right] > dp[left][right]) {
                    dp[left][right] = dp[left+1][right];
                    p[left][right] = 2;
                }
                if (dp2[left+1][right-1] % 2==0) {
                    dp2[left][right] = dp2[left+1][right-1];
                    p2[left][right] = 4;
                }
                if (dp2[left][right-1] % 2==0 && dp2[left][right-1] > dp2[left][right]) {
                    dp2[left][right] = dp2[left][right-1];
                    p2[left][right] = 3;
                }
                if (dp2[left+1][right] % 2==0 && dp2[left+1][right] > dp2[left][right]) {
                    dp2[left][right] = dp2[left+1][right];
                    p2[left][right] = 2;
                }
                if (dp[left+1][right-1] % 2==1 && s.charAt(left)==s.charAt(right) && dp[left+1][right-1]+2 > dp[left][right]) {
                    dp[left][right] = dp[left+1][right-1]+2;
                    p[left][right] = 1;
                }
                if (dp2[left+1][right-1] % 2==0 && s.charAt(left)==s.charAt(right) && dp2[left+1][right-1]+2 > dp2[left][right]) {
                    dp2[left][right] = dp2[left+1][right-1]+2;
                    p2[left][right] = 1;
                }
            }
        }
        int left1 = 0, right1 = 0, max1 = 0, left2 = 0, right2 = 0, max2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (dp[i][j] > max1 && dp[i][j] <= 100) {
                    max1 = dp[i][j];
                    left1 = i;
                    right1 = j;
                }
                if (dp2[i][j] > max2 && dp2[i][j] <= 100) {
                    max2 = dp2[i][j];
                    left2 = i;
                    right2 = j;
                }
            }
        }
        f = false;
        if (max1 > max2) {
            f = true;
            System.out.println(getans(left1, right1, p));
        }
        else
            System.out.println(getans(left2, right2, p2));
        pw.close();
    }
    private static String getans(int left, int right, int[][]p) {
        if (left > right)
            return "";
        if (left==right) {
            if (f)
                return s.charAt(left)+"";
            return "";
        }
        if (p[left][right]==1)
            return s.charAt(left)+getans(left+1, right-1, p)+s.charAt(right);
        else if (p[left][right]==2)
            return getans(left+1, right, p);
        else if (p[left][right]==3)
            return getans(left, right-1, p);
        else
            return getans(left+1, right-1, p);
    }
    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    private static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    private static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    private static String next() throws IOException {
        while (st==null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}
/*
hbunaloeaeruvshngzygjipskinglhnzdceytngxxrtepoxhmistbfptebvhebngpsiaaumououxttryatthdthyibcaphgniuyvgniribgiywrhduuxzjnadbdgpxnhxtahogohofcgxtctpbxdbgmgbatrxnqutuxznoryyuihdqfcgydobzhndobiuupdexehydoaibbbihtxuoenirriiojkvdeyhznggnbzrdynacpzwozrkizedotobltxzppopkztbrojzkzjnlxvdtoniljbidxxxkytytpnizjhroroyobizklkyopxdnpobwpgcvdkijoiabdbpecinganrytfndbuxiyxzbqgooyhreunextqaeixpyamhupycririhchtzyfpiejdnrxabguiyiyooghppdhauiegdwtnapurzigoaugzvddcxypbbimneisuehdghhzvfnngoyhgrgxresnaxiimygchgxuheeaxrnyizelokuxsga
*/