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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author vadimmm
 */
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 {
    private int[][] dp, left, right;
    private char[] string;
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        string = in.next().toCharArray();
        if (string.length > 2574) {
            int[] counter = new int[26];
            for (char ch : string)
                counter[ch - 'a']++;
            char answer = 'a';
            for (int i = 0; i < 26; ++i)
                if (counter[i] >= 100) {
                    answer += i;
                    break;
                }
            for (int i = 0; i < 100; ++i)
                out.print(answer);
        } else {
            int length = string.length;
            dp = new int[length][length];
            left = new int[length][length];
            right = new int[length][length];
            for (int i = 0; i < length; ++i) {
                dp[i][i] = 1;
                left[i][i] = i;
                right[i][i] = i;
            }
            int max = find(0, length - 1);
            boolean odd = (max & 1) == 1;
            max = Math.min(max, 100);
            if (max < 100) {
                max >>= 1;
                int l = 0;
                int r = length - 1;
                List<Character> answer = new ArrayList<Character>(max);
                for (int i = 0; i < max; ++i) {
                    int tl = left[l][r];
                    int tr = right[l][r];
                    answer.add(string[tl]);
                    l = tl + 1;
                    r = tr - 1;
                }
                for (char ch : answer)
                    out.print(ch);
                if (odd)
                    out.print(string[l]);
                Collections.reverse(answer);
                for (char ch : answer)
                    out.print(ch);
            }
            else {
                max = 50;
            
            int l = 0;
            int r = length - 1;
            List<Character> answer = new ArrayList<Character>(max);
            for (int i = 0; i < max; ++i) {
                int tl = left[l][r];
                int tr = right[l][r];
                answer.add(string[tl]);
                l = tl + 1;
                r = tr - 1;
            }
            for (char ch : answer)
                out.print(ch);
            Collections.reverse(answer);
            for (char ch : answer)
                out.print(ch);
            }
        }
        out.println();
    }
    private int find(int from, int to) {
        if (dp[from][to] != 0)
            return dp[from][to];
        int three = 0;
        if (string[from] == string[to])
            if (from + 1 == to)
                three = 2;
            else
                three = 2 + find(from + 1, to - 1);
        int one = find(from + 1, to);
        int two = find(from, to - 1);
        if (one > two && one > three) {
            left[from][to] = left[from + 1][to];
            right[from][to] = right[from + 1][to];
            return dp[from][to] = one;
        } else if (two > three) {
            left[from][to] = left[from][to - 1];
            right[from][to] = right[from][to - 1];
            return dp[from][to] = two;
        } else {
            left[from][to] = from;
            right[from][to] = to;
            return dp[from][to] = three;
        }
    }
}

class InputReader {

    private static BufferedReader bufferedReader;
    private static StringTokenizer stringTokenizer;

    public InputReader(InputStream inputStream) {
        bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        stringTokenizer = null;
    }

    public String next() {
        while(stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            try {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return stringTokenizer.nextToken();
    }

    }