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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;


public class PALINDROME {

    private static char[] c;
    static int index = 0;
    private static int[][] dp = new int[2601][2601];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); 
        String val = in.next();
        c = val.toCharArray();
        if (c.length >= 2600) {
            int[] count = new int[26];
            for (int i = 0; i < c.length; i++) {
                count[c[i] - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                if (count[i] >= 100) {
                    for (int j = 0; j < 100; j++) {
                        System.out.print((char) ('a' + i));
                    }
                    break;
                }
            }
        } else {
            int max = cal(0, c.length - 1);
            char[] result = new char[max];
            trace(0, c.length - 1, result);
            if (max <= 100) {
                System.out.println(result);
            } else {
                for (int i = 0; i < 50; i++) {
                    System.out.print(result[i]);
                }
                for (int i = 0; i < 50; i++) {
                    System.out.print(result[max - 50 + i]);
                }
            }
        }
        //  System.out.println(max);
        System.out.close();


    }

    public static int cal(int start, int end) {


        if (start > end) {
            return 0;
        }
        if (start == end) {
            return 1;
        }
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        if (c[start] == c[end]) {
            dp[start][end] = 2 + cal(start + 1, end - 1);
        } else {
            dp[start][end] = Math.max(cal(start + 1, end), cal(start, end - 1));
        }
        return dp[start][end];
    }

    public static void trace(int x, int y, char[] re) {
        if (x > y) {
            return;
        }
        if (x == y) {
            re[index++] = c[x];
            return;
        }
        if (c[x] == c[y]) {
            re[index++] = c[x];
            trace(x + 1, y - 1, re);
            re[index++] = c[y];
        } else {
            if (dp[x + 1][y] > dp[x][ y - 1]) {
                trace(x + 1, y, re);
            } else {
                trace(x, y - 1, re);
            }
        }
    }

    
}