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:
// practice with kaiboy
import java.io.*;
import java.util.*;

public class CF335B extends PrintWriter {
	CF335B() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF335B o = new CF335B(); o.main(); o.flush();
	}

	static final int A = 26;
	char[] cc;
	int[][] dp;
	void solve(int i, int j, int k) {
		if (i > j)
			return;
		while (i < j && cc[i] != cc[j])
			if (dp[i + 1][j] > dp[i][j - 1])
				i++;
			else
				j--;
		print(cc[i]);
		k++;
		if (i < j) {
			if (k < 50)
				solve(i + 1, j - 1, k);
			print(cc[j]);
		}
	}
	void main() {
		cc = sc.next().toCharArray();
		int n = cc.length;
		int[] kk = new int[A];
		for (int i = 0; i < n; i++) {
			int a = cc[i] - 'a';
			if (++kk[a] == 100) {
				while (kk[a]-- > 0)
					print(cc[i]);
				println();
				return;
			}
		}
		dp = new int[n][n];
		for (int i = n - 1; i >= 0; i--) {
			dp[i][i] = 1;
			for (int j = i + 1; j < n; j++)
				dp[i][j] = cc[i] == cc[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);
		}
		solve(0, n - 1, 0);
		println();
	}
}