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 d {
public static void main(String[] args) throws IOException {
	input.init(System.in);
	PrintWriter out = new PrintWriter(System.out);
	s = input.next().toCharArray();
	n = s.length;
	int[] fs = new int[26];
	for(int i = 0; i<n; i++)
	{
		fs[s[i]-'a']++;
	}
	boolean found = false;
	for(int i = 0; i<26 && !found; i++)
	{
		if(fs[i] >= 100)
		{
			for(int j = 0; j<100; j++)
				out.print((char)('a'+i));
			out.println();
			found = true;
		}
	}
	if(!found)
	{
		memo = new int[n][n];
		for(int[] A : memo) Arrays.fill(A, -1);
		go(0, n-1);
		pal1="";
		middle="";
		pal2="";
		trace(0, n-1);
		if(pal1.length() > 50)
		{
			pal1 = pal1.substring(0,50);
			pal2 = pal2.substring(pal2.length()-50);
		}
		if(pal1.length() == 50) out.println(pal1+pal2);
		else out.println(pal1+middle+pal2);
	}
	out.close();
}
static int[][] memo;
static String pal1, pal2;
static String middle;
static char[] s;
static int n;
static int go(int a, int b)
{
	if(a > b) return 0;
	if(a == b) return 1;
	if(memo[a][b] != -1) return memo[a][b];
	int max = Math.max(go(a+1, b), go(a,b-1));
	if(s[a] == s[b]) max = Math.max(go(a+1, b-1)+2, max);
	return memo[a][b] = max;
}
static void trace(int a, int b)
{
	if(a>b) return;
	if(a == b)
	{
		middle += s[a];
		return;
	}
	int m1 = go(a+1, b);
	int m2 = go(a, b-1);
	int max = Math.max(m1, m2);
	if(s[a] == s[b] && go(a+1, b-1)+2 > max)
	{
		pal1 = pal1 + s[a];
		pal2 = s[b] + pal2;
		trace(a+1, b-1);
	}
	else if(m1 > m2)
	{
		trace(a+1, b);
	}
	else trace(a, b-1);
	
}
public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}