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.StringTokenizer;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author Trung Pham
 */
public class B {

    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();
        PrintWriter out = new PrintWriter(System.out);
        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++) {
                        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) {
                out.println(result);
            } else {
                for (int i = 0; i < 50; i++) {
                    out.print(result[i]);
                }
                for (int i = 0; i < 50; i++) {
                    out.print(result[max - 50 + i]);
                }
            }
        }
        //  System.out.println(max);
        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);
            }
        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() {
            //System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {


            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}