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

public class B {

	BufferedReader in;
	StringTokenizer st;
	PrintWriter out;

	String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

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

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

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

	public static char[] getLCS(char[] x, char[] y) {
		int m = x.length;
		int n = y.length;
		int[][] len = new int[m + 1][n + 1];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (x[i] == y[j]) {
					len[i + 1][j + 1] = len[i][j] + 1;
				} else {
					len[i + 1][j + 1] = Math.max(len[i + 1][j], len[i][j + 1]);
				}
			}
		}
		int cnt = len[m][n];
		char[] res = new char[cnt];
		for (int i = m - 1, j = n - 1; i >= 0 && j >= 0;) {
			if (x[i] == y[j]) {
				res[--cnt] = x[i];
				--i;
				--j;
			} else if (len[i + 1][j] > len[i][j + 1]) {
				--j;
			} else {
				--i;
			}
		}
		return res;
	}

	void solve() throws Exception {
		String s = next();

		int cnt[] = new int[666];
		for (char c : s.toCharArray())
			cnt[c]++;
		for (int i = 0; i < 666; i++)
			if (cnt[i] >= 100) {
				for (int j = 0; j < 100; j++)
					out.print((char) (i));
				return;
			}

		char ans[] = getLCS(s.toCharArray(), (new StringBuilder(s)).reverse()
				.toString().toCharArray());
		String sa = new String(ans);
		
		if (sa.length() > 100) {
			// System.err.println(sa);
			if (sa.length() % 2 == 1)
				sa = sa.substring(0, sa.length() / 2)
						+ sa.substring(sa.length() / 2 + 1);
			while (sa.length() > 100) {
				sa = sa.substring(0, sa.length() / 2 - 1)
						+ sa.substring(sa.length() / 2 + 1);
				// System.err.println(sa);
			}
		}
		System.err.println(sa);
		out.println(sa);
	}

	void run() {
		try {
			Locale.setDefault(Locale.US);
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
			solve();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	public static void main(String[] args) {
		new B().run();
	}

}