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

public class B {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		S = in.next().toCharArray();
		int[] cnt = new int[26];
		for(int i=0; i<S.length; i++)
			cnt[S[i]-'a']++;
		for(int i=0; i<26; i++) {
			if(cnt[i]>=100) {
				for(int j=0; j<100; j++)
					System.out.print((char)('a'+i));
				System.out.println();
				return;
			}
		}
		
		DP = new Integer[S.length][S.length];
		int lo = 0;
		int hi = S.length-1;
		String ans = "";
		while(true) {
			if(lo>hi) {
				System.out.print(ans);
				System.out.println(new StringBuilder(ans).reverse().toString());
				return;
			}
			if(lo==hi || ans.length()>=50) {
				System.out.print(ans);
				if(ans.length() < 50) System.out.print(S[lo]);
				System.out.println(new StringBuilder(ans).reverse().toString());
				return;
			}
			if(S[lo]==S[hi]) {
				ans += S[lo];
				lo++;
				hi--;
			} else if(f(lo,hi)==f(lo+1,hi)) {
				lo++;
			} else {
				hi--;
			}
		}
	}
	
	static Integer[][] DP;
	static char[] S;
	static int f(int lo, int hi) {
		if(lo > hi) return 0;
		if(lo == hi) return 1;
		if(DP[lo][hi]!=null) return DP[lo][hi];
		if(S[lo]==S[hi]) return DP[lo][hi]=2+f(lo+1,hi-1);
		return DP[lo][hi]=Math.max(f(lo+1,hi), f(lo,hi-1));
	}
}