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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Liavontsi Brechka
 */
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();
    }

    static
    @SuppressWarnings("Duplicates")
    class TaskB {
        String s;
        int n;
        int[][] dp;
        StringBuilder res;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            s = in.next();
            n = s.length();

            int[] count = new int[26];
            for (int i = 0; i < n; i++) count[s.charAt(i) - 'a']++;
            for (int i = 0; i < 26; i++) {
                if (count[i] >= 100) {
                    res = new StringBuilder();
                    for (int j = 0; j < 100; j++) res.append((char) (i + 'a'));
                    out.print(res);
                    return;
                }
            }

            dp = new int[n][n];
            for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);
            next(0, n - 1);

            res = new StringBuilder();

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] >= 100) {
                        genRes(i, j, 100);
                        out.print(res);
                        return;
                    }
                }
            }

            genRes(0, n - 1, dp[0][n - 1]);
            out.print(res);
        }

        private int next(int l, int r) {
            if (dp[l][r] != -1) return dp[l][r];

            if (l == r) return dp[l][r] = 1;

            if (s.charAt(l) == s.charAt(r)) {
                if (l + 1 == r) return dp[l][r] = 2;
                else return dp[l][r] = next(l + 1, r - 1) + 2;
            } else return dp[l][r] = Math.max(next(l + 1, r), next(l, r - 1));
        }

        private void genRes(int l, int r, int rem) {
            if (rem == 0) {
                StringBuilder right = new StringBuilder(res);
                right.reverse();
                res.append(right);
                return;
            }

            if (l == r) {
                StringBuilder right = new StringBuilder(res);
                right.reverse();
                res.append(s.charAt(l));
                res.append(right);
                return;
            }

            if (s.charAt(l) == s.charAt(r)) {
                res.append(s.charAt(l));
                if (l + 1 == r) {
                    StringBuilder right = new StringBuilder(res);
                    right.reverse();
                    res.append(right);
                } else {
                    genRes(l + 1, r - 1, rem - 2);
                }
            } else {
                if (dp[l + 1][r] > dp[l][r - 1]) genRes(l + 1, r, rem);
                else genRes(l, r - 1, rem);
            }
        }

    }

    static class InputReader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(readLine());
            }
            return tokenizer.nextToken();
        }

        public String readLine() {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

    }
}