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

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

class TaskB {
    public void solve(int testNumber, FastScanner in, PrintWriter out) {
        char[] s = in.next().toCharArray();
        int[][] positions = new int[26][];
        int[] cnt = new int[26];
        for (int i = 0; i < s.length; i++) {
            int c = s[i] - 'a';
            ++cnt[c];
        }
        for (int i = 0; i < 26; i++) {
            positions[i] = new int[cnt[i]];
            cnt[i] = 0;
        }
        for (int i = 0; i < s.length; i++) {
            int c = s[i] - 'a';
            positions[c][cnt[c]] = i;
            ++cnt[c];
        }

        int n = s.length;
        final int N = 101;
        int[][] leftmost = new int[N][n];
        int[][] next = new int[N][n];
        for (int[] arr : leftmost) {
            Arrays.fill(arr, -1);
        }
        for (int[] arr : next) {
            Arrays.fill(arr, -1);
        }
        for (int i = 0; i < n; i++) {
            leftmost[1][i] = i;
        }
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            leftmost[2][i] = findLeftmost(positions[c], i);
        }
        for (int len = 3; len < N; len++) {
            int minL = n;
            int minR = n;
            for (int i = n - 1; i >= 0; i--) {
                int c = s[i] - 'a';
                int cur = findLeftmost(positions[c], minR);
                if (cur >= 0) {
                    next[len][i] = minL;
                    leftmost[len][i] = cur;
                }
                int r = leftmost[len - 2][i];
                if (r >= 0 && minR > r) {
                    minL = i;
                    minR = r;
                }
            }
        }
        int len = N - 1;
        int start = -1;
        outer:
        while (len > 0) {
            for (int i = 0; i < n; i++) {
                if (leftmost[len][i] >= 0) {
                    start = i;
                    break outer;
                }
            }
            --len;
        }
        TreeSet<Integer> ans = new TreeSet<Integer>();
        while (len > 0) {
            ans.add(start);
            ans.add(leftmost[len][start]);
            start = next[len][start];
            len -= 2;
        }
        for (int x : ans) {
            out.print(s[x]);
        }
    }

    private int findLeftmost(int[] a, int from) {
        int l = -1;
        int r = a.length;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (a[m] <= from) {
                l = m;
            } else {
                r = m;
            }
        }
        if (r == a.length) {
            return -1;
        }
        return a[r];
    }
}

class FastScanner {

    private BufferedReader in;
    private StringTokenizer st;

    public FastScanner(InputStream stream) {
        in = new BufferedReader(new InputStreamReader(stream));
    }

    public String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }

    }