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:
//package codeforces.train;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class ProblemB {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    long[] ttl = null;
    int txl = 0;
    long readLong() throws IOException {
        if(ttl == null || txl >= ttl.length) {
            ttl = readLongs();
            txl = 0;
        }
        return ttl[txl++];
    }

    long[] readLongs() throws IOException {
        String[] strings = reader.readLine().split(" ");
        long[] longs = new long[strings.length];
        for(int i = 0; i < longs.length; i++) {
            longs[i] = Long.parseLong(strings[i]);
        }
        return longs;
    }

    int[] readInts() throws IOException {
        String[] strings = reader.readLine().split(" ");
        int[] ints = new int[strings.length];
        for(int i = 0; i < ints.length; i++) {
            ints[i] = Integer.parseInt(strings[i]);
        }
        return ints;
    }

    int[] tt = null;
    int tx = 0;
    int readInt() throws IOException {
        if(tt == null || tx >= tt.length) {
            tt = readInts();
            tx = 0;
        }
        return tt[tx++];
    }

    void solve() throws IOException {
        char[] s = reader.readLine().toCharArray();
        int n = s.length;
        int[][] di = new int[n][26];
        for(int i = 0; i < 26; i++) {
            di[0][i] = -1;
        }
        di[0][s[0] - 'a'] = 0;
        for(int i = 1; i < n; i++) {
            System.arraycopy(di[i - 1], 0, di[i], 0, 26);
            di[i][s[i] - 'a'] = i;
        }
        int[][] dp = new int[n + 1][51];
        for(int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }
        for(int i = 0; i < n; i++) {
            dp[i][0] = n - 1;
        }
        int curm = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 50; j++) {
                dp[i + 1][j + 1] = dp[i][j + 1];
                if(dp[i][j] > i) {
                    int l = s[i] - 'a';
                    int p = dp[i][j];
                    if(di[p][l] > i) {
                        curm = Math.max(curm, j + 1);
                        dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], di[p][l] - 1);
                    }
                }
            }
        }
//        writer.println(curm);
        if(curm == 0) {
            writer.println(s[0]);
            writer.flush();
            return;
        }
        int ix = -1;
        int ix2 = -1;
//        while(dp[ix][curm] == 0) ix++;
        for(int i = 1; i <= n; i++) {
            if(dp[i][curm] != dp[i - 1][curm]) {
                int p = dp[i][curm];
                if((p + 1) - (i - 1) > 1) {
                    ix2 = i;
                    break;
                }
                if(ix == -1) {
                    ix = i;
                }
            }
        }
        if(ix2 != -1) ix = ix2;
        int jx = ix;
        StringBuffer ans = new StringBuffer();
        ans.append(s[jx - 1]);
        jx--;
        for(int i = curm - 1; i > 0; i--) {
            while(dp[jx][i] == dp[jx - 1][i]) jx--;
            ans.append(s[jx - 1]);
            jx--;
        }
        String suffix = ans.toString();
        String prefix = ans.reverse().toString();
        if(curm == 50) {
            writer.println(prefix + suffix);
        }
        else {
            int i = 0, j = n - 1;
            for(char c: prefix.toCharArray()) {
                while(s[i] != c) i++;
                i++;
                while(s[j] != c) j--;
                j--;
            }
            if(i <= j) {
                prefix += s[i];
            }
            writer.println(prefix + suffix);
        }
        writer.flush();
    }

    void multiSolve() throws IOException {
        int n = readInts()[0];
        for(int i = 0; i < n; i++) {
            if(i > 0) writer.println();
            solve();
        }
    }

    public static void main(String[] args) throws IOException{
        new ProblemB().solve();
    }
}