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.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;

public class ProblemB {
	
	static final int INF = -1;
	
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		char[] s = in.next().toCharArray();
		int len = s.length;
		
		int[][] next = new int[len][26];
		int[][] prev = new int[len][26];
		int[] firstSeen = new int[26];
		Arrays.fill(firstSeen, len);
		for (int i = len-1 ; i >= 0 ; i--) {
			int si = s[i] - 'a';
			for (int j = 0 ; j < 26 ; j++) {
				next[i][j] = firstSeen[j]; 
			}
			firstSeen[si] = i;
		}
		int[] lastSeen = new int[26];
		Arrays.fill(lastSeen, -1);
		for (int i = 0 ; i < len ; i++) {
			int si = s[i] - 'a';
			for (int j = 0 ; j < 26 ; j++) {
				prev[i][j] = lastSeen[j]; 
			}
			lastSeen[si] = i;
		}
		
		int[][] dp = new int[len+1][51];
		int[][] dp_prv = new int[len+1][51];
		for (int i = 0 ; i <= len ; i++) {
			Arrays.fill(dp[i], INF);
		}
		for (int i = 0 ; i < len ; i++) {
			dp[i][1] = (i < lastSeen[s[i]-'a']) ? lastSeen[s[i]-'a'] : INF;
		}
		for (int i = 0 ; i < len ; i++) {
			for (int j = 1 ; j < 50 ; j++) {
				if (dp[i][j] == INF) {
					continue;
				}
				for (int nx = 0 ; nx < 26 ; nx++) {
					int prv = prev[dp[i][j]][nx];
					int nxt = next[i][nx];
					if (prv <= nxt) {
						continue;
					}
					if (dp[nxt][j+1] < prv) {
						dp[nxt][j+1] = prv;
						dp_prv[nxt][j+1] = i;
					}
				}
			}
		}
		
		int useJ = -1;
		int useI = -1;
		int maxLen = 0;
		for (int j = 50 ; j >= 0 ; j--) {
			boolean found = false;
			for (int i = 0 ; i < len ; i++) {
				if (dp[i][j] != INF) {
					int ln = j * 2;
					if (i + 1 < dp[i][j]) {
						ln++;
					}
					if (maxLen < ln) {
						maxLen = ln;
						useJ = j;
						useI = i;
					}
					found = true;
				}
			}
			if (found) {
				break;
			}
		}
		if (maxLen == 0) {
			out.println(s[0]);
			out.flush();
			return;
		}
		
		int nowJ = useJ;
		int nowI = useI;
		char[] ans = new char[useJ];
		while (nowJ >= 1) {
			ans[nowJ-1] = s[nowI];
			int ti = dp_prv[nowI][nowJ];
			nowI = ti;
			nowJ--;
		}
		String prefix = String.valueOf(ans);
		String suffix = new StringBuilder(prefix).reverse().toString();
		
		if (maxLen < 100 && maxLen % 2 == 1) {
			out.println(prefix + s[useI+1] + suffix);
		} else {
			out.println(prefix + suffix);
		}
		out.flush();
	}

	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}