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.Arrays;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.math.BigInteger;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Comparator;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author shu_mj @ http://shu-mj.com
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    Scanner in;
    PrintWriter out;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        this.in = in;
        this.out = out;
        run();
    }

    void run() {
        char[] cs = in.next().toCharArray();
        int n = cs.length;
        int[][] bs = new int[26][n + 1];
        Algo.fill(bs, -1);
        for (int i = 0; i < n; i++) {
            bs[cs[i] - 'a'][i] = i;
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 1; j <= n; j++) {
                if (bs[i][j] != j) bs[i][j] = bs[i][j - 1];
            }
        }
        int[][] dp = new int[n + 1][51];
        int[][] pre = new int[n + 1][51];
        Algo.fill(dp, -1);
        dp[0][0] = n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 50; j++) {
                dp[i + 1][j] = dp[i][j];
                pre[i + 1][j] = 0;
            }
            for (int j = 0; j < 50; j++) {
                if (dp[i][j] > i + 1 && bs[cs[i] - 'a'][dp[i][j] - 1] > i) {
                    int res = bs[cs[i] - 'a'][dp[i][j] - 1];
                    if (dp[i + 1][j + 1] < res) {
                        dp[i + 1][j + 1] = res;
                        pre[i + 1][j + 1] = 1;
                    }
//                    Algo.debug(i, j, dp[i][j], res);
                }
            }
        }
        int ri = 0, rj = 0;
        outer: for (int j = 50; j >= 0; j--) {
            for (int i = 0; i < n; i++) {
                if (dp[i][j] > -1) {
                    ri = i;
                    rj = j;
                    break outer;
                }
            }
        }
        if (rj < 50 && dp[ri][rj] == ri) {
            for (int i = 0; i <= n; i++) {
                if (dp[i][rj] > i) {
                    ri = i;
                    break;
                }
            }
        }
        char[] res = new char[rj];
        for (int i = ri, j = rj; i > 0; i--) {
            if (pre[i][j] == 1) {
                res[j - 1] = cs[i - 1];
                j--;
            }
        }
        out.print(res);
        if (rj < 50 && dp[ri][rj] > ri) {
            out.print(cs[ri]);
        }
        Algo.reverse(res);
        out.println(res);
    }
}

class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
        eat("");
    }

    private void eat(String s) {
        st = new StringTokenizer(s);
    }

    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null)
                return false;
            eat(s);
        }
        return true;
    }

    public String next() {
        hasNext();
        return st.nextToken();
    }

}

class Algo {


    public static void swap(char[] cs, int i, int j) {
        char t = cs[i]; cs[i] = cs[j]; cs[j] = t;
    }

    public static void reverse(char[] cs) {
        reverse(cs, 0, cs.length);
    }

    public static void reverse(char[] cs, int b, int e) {
        while (b < e) swap(cs, b++, --e);
    }

    public static void fill(int[][] iss, int v) {
        for (int[] is : iss) Arrays.fill(is, v);
    }

}