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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

import static java.util.Arrays.deepToString;

public class B {
	final static int LEN = 100, ALPH = 26;

	static void get(char[] s) {
		int[][] next = new int[ALPH][s.length + 1];
		for (int ch = 0; ch < ALPH; ch++) {
			char c = (char) (ch + 'a');
			next[ch][s.length] = s.length;
			for (int i = s.length - 1; i >= 0; i--) {
				next[ch][i] = next[ch][i + 1];
				if (s[i] == c) {
					next[ch][i] = i;
				}
			}
		}

		int[][] d = new int[LEN + 1][s.length];
		for (int[] dd : d) {
			Arrays.fill(dd, -1);
		}
		for (int i = 0; i < s.length; i++) {
			d[0][i] = i - 1;
			d[1][i] = i;
		}
		for (int from = s.length - 2; from >= 0; from--) {
			int ch = s[from] - 'a';
			for (int wantLen = 2; wantLen <= LEN; wantLen++) {
				d[wantLen][from] = d[wantLen][from + 1];
				int to = d[wantLen - 2][from + 1];
				if (to == -1)
					continue;
				if (next[ch][to + 1] != s.length && (d[wantLen][from] == -1 || next[ch][to + 1] < d[wantLen][from])) {
					d[wantLen][from] = next[ch][to + 1];
				}
			}
		}
		for (int ansLen = LEN; ansLen > 0; ansLen--) {
			if (d[ansLen][0] != -1) {
				// writer.println(ansLen);
				int from = 0;
				String pref = "", mid = "", suff = "";
				while (ansLen > 0) {
					if (ansLen == 1) {
						mid = s[from] + "";
						break;
					}
					if (d[ansLen][from] == d[ansLen][from + 1]) {
						from++;
						continue;
					}
					pref = pref + s[from];
					suff = s[from] + suff;
					ansLen -= 2;
					from++;
				}
				writer.println(pref + mid + suff);
				return;
			}
		}
	}

	static void solve() {
		// StringBuffer sb = new StringBuffer();
		// Random rng = new Random(50);
		// for (int i = 0; i < 10; i++) {
		// sb.append((char) ('a' + rng.nextInt(26)));
		// }
		// get(sb.toString().toCharArray());
		// debug("here");
		// if (true)
		// return;
		get(next().toCharArray());
	}

	public static void main(String[] args) throws Exception {
		reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new PrintWriter(System.out);
		Locale.setDefault(Locale.US);

		setTime();
		solve();
		printTime();
		printMemory();

		writer.close();
	}

	static BufferedReader reader;
	static PrintWriter writer;
	static StringTokenizer tok = new StringTokenizer("");
	static long systemTime;

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

	static void setTime() {
		systemTime = System.currentTimeMillis();
	}

	static void printTime() {
		System.err.println("Time consumed: " + (System.currentTimeMillis() - systemTime));
	}

	static void printMemory() {
		System.err.println("Memory consumed: "
				+ (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1000 + "kb");
	}

	static String next() {
		while (!tok.hasMoreTokens()) {
			String w = null;
			try {
				w = reader.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			if (w == null)
				return null;
			tok = new StringTokenizer(w);
		}
		return tok.nextToken();
	}

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

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

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

	static BigInteger nextBigInteger() {
		return new BigInteger(next());
	}
}