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.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Throwable {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String os = br.readLine();
        String rs = new StringBuilder(os).reverse().toString();
        char[] s = os.toCharArray();
        char[] t = rs.toCharArray();
        int[] f = new int[26];
        for (int i = 0; i < s.length; i++)
            f[s[i]-'a']++;
        for (int i = 0; i < 26; i++)
            if (f[i] >= 100) {
                StringBuilder sb = new StringBuilder();
                char c = (char) ('a' + i);
            	for (int j = 0; j < 100; j++)
                    sb.append(c);
                System.out.println(sb.toString());
                return;
            }
        int n = s.length;
        int[][] dp = new int[n+1][n+1];
        int[][] px = new int[n+1][n+1];
        int[][] py = new int[n+1][n+1];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        for (int i = 0; i <= n; i++)
            dp[i][0] = dp[0][i] = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (s[i] == t[j]) {
                    if (dp[i+1][j+1] < dp[i][j] + 1) {
                    	dp[i+1][j+1] = dp[i][j] + 1;
                        px[i+1][j+1] = i;
                        py[i+1][j+1] = j;
                    }
                }
        		else {
                	if (dp[i+1][j+1] < dp[i+1][j]) {
                    	dp[i+1][j+1] = dp[i+1][j];
                        px[i+1][j+1] = i + 1;
                        py[i+1][j+1] = j;
                    }
                    if (dp[i+1][j+1] < dp[i][j+1]) {
                    	dp[i+1][j+1] = dp[i][j+1];
                        px[i+1][j+1] = i;
                        py[i+1][j+1] = j + 1;
                    }
                    if (dp[i+1][j+1] < dp[i][j]) {
                        dp[i+1][j+1] = dp[i][j];
                        px[i+1][j+1] = i;
                        py[i+1][j+1] = j;
                    }
                }
        StringBuilder sb = new StringBuilder();
        int cx = n, cy = n;
        while (cx != 0 || cy != 0) {
            int ppx = px[cx][cy];
            int ppy = py[cx][cy];
            if (ppx != cx && ppy != cy)
                sb.append(s[ppx]);
            cx = ppx;
            cy = ppy;
        }
        String ans = sb.toString();
        if (ans.length() <= 100)
        	System.out.println(ans);
        else {
            System.out.print(ans.substring(0, 50));
            System.out.println(new StringBuilder(ans.substring(0, 50)).reverse().toString());
        }
    }
}