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.*;
import java.math.BigInteger;
import java.util.*;

public class memSQL {

    public static void main(String[] args) throws IOException {
        new memSQL().run();
    }

    static final int MAXSZ = 3100;
    int[][] dp;
    int[][] tol;
    int[][] tor;
    boolean[][] print;
    String s;
    int len;

    int calc(int i, int j) {
        if(i < 0 || j < 0 || i >= len || j >= len) return 0;
        if(dp[i][j] != -1)
            return dp[i][j];
        if(i > j)
            return dp[i][j] = 0;

        if(s.charAt(i) == s.charAt(j)) {
            print[i][j] = true;
            tol[i][j] = i + 1;
            tor[i][j] = j - 1;
            return dp[i][j] = calc(i + 1, j - 1) + (i == j ? 1 : 2);
        }

        int movel = calc(i + 1, j);
        int mover = calc(i, j - 1);
        if(movel > mover) {
            tol[i][j] = i + 1;
            tor[i][j] = j;
            return dp[i][j] = movel;
        }
        else {
            tol[i][j] = i;
            tor[i][j] = j - 1;
            return dp[i][j] = mover;
        }
    }

    void init() {
        for(int i = 0; i < dp.length; ++i)
            for(int j = 0; j < dp[i].length; ++j) {
                tol[i][j] = tor[i][j] = dp[i][j] = -1;
                print[i][j] = false;
            }
    }

    void solve() throws IOException {
        s = nextToken();
        len = s.length();

        if(s.length() > 3000) {
            int cnt[] = new int[300];
            for(int i = 0; i < s.length(); ++i)
                cnt[s.charAt(i)]++;
            for(int i = 0; i < cnt.length; ++i)
                if(cnt[i] >= 100) {
                    StringBuilder b = new StringBuilder();
                    for(int j = 0; j < 100; ++j) b.append((char)i);
                    out.println(b.toString());
                    return;
                }
        }

        dp = new int[MAXSZ][MAXSZ];
        tol = new int[MAXSZ][MAXSZ];
        tor = new int[MAXSZ][MAXSZ];
        print = new boolean[MAXSZ][MAXSZ];

        init();
        int maxc = calc(0, len - 1);

        StringBuilder bl = new StringBuilder();
        StringBuilder br = new StringBuilder();

        int rem = Math.min(100, maxc);
        int l = 0, r = len - 1;
        int lastl = 0, lastr = len - 1;
        while(rem > 0) {
            if(print[l][r]) {
                bl.append(s.charAt(l));
                --rem;
                if(l < r) {
                    br.insert(0, s.charAt(r));
                    --rem;
                }
            }
            lastl = l;
            lastr = r;
            l = tol[lastl][lastr];
            r = tor[lastl][lastr];
        }

        String res = bl.toString() + br.toString();
        out.println(res);
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    public String nextToken() throws IOException {
        while(st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

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

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

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

    void run() throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;

        br = new BufferedReader( new InputStreamReader( oj ? System.in : new FileInputStream("input.txt")));
        out = new PrintWriter( oj ? System.out : new FileOutputStream("output.txt"));

        solve();

        out.close();
    }

}