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 static java.lang.Math.*;

public class B {

	private final static boolean autoflush = false;

	public B () {
		char [] C = sc.nextChars();

		int [] L = new int [200];
		for (char c : C)
			++L[c];

		for (char c = 'a'; c <= 'z'; ++c)
			if (L[c] >= 100) {
				StringBuilder B = new StringBuilder();
				for (int i = 0; i < 100; ++i)
					B.append(c);
				exit(B);
			}

		int N = C.length;
		int [][] F = new int [N+1][N+1];
		for (int i = N-1; i >= 0; --i) {
			F[i][i+1] = 1;
			for (int j = i+1; j < N; ++j) {
				F[i][j+1] = max(F[i][j], F[i+1][j+1]);
				if (C[i] == C[j])
					F[i][j+1] = max(F[i][j+1], 2 + F[i+1][j]);
			}
		}

		int K = 0, P = -1, Q = -1;
		out: for (int i = 0; i <= N; ++i)
			for (int j = 0; j <= N; ++j) {
				if (F[i][j] > K) {
					P = i; Q = j; K = F[i][j];
				}
				if (K >= 100)
					break out;
			}

		String S = "", T = ""; int X = K;
		while (S.length() + T.length() < K)
			if (Q == P+1)
				S += C[P];
			else if (F[P][Q-1] == X)
				--Q;
			else if (F[P+1][Q] == X)
				++P;
			else if (C[P] == C[Q-1]) {
				S += C[P]; T = C[P] + T;
				++P; --Q; X -= 2;
			}

		String V = S + T;
		if (V.length() > 100)
			V = V.substring(0, 50) + V.substring(V.length() - 50);

		exit(V);
	}

	////////////////////////////////////////////////////////////////////////////////////
	private final static MyScanner sc = new MyScanner();
	private static class MyScanner {
		public String next() { newLine(); return line[index++]; }
		public char [] nextChars() { return next ().toCharArray (); }
		//////////////////////////////////////////////
		private boolean eol() { return index == line.length; }
		private String readLine() {
			try {
				return r.readLine();
			} catch (Exception e) {
				throw new Error (e);
			}
		}
		private final java.io.BufferedReader r;
		private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
		private MyScanner (java.io.BufferedReader r) {
			try {
				this.r = r;
				while (!r.ready())
					Thread.sleep(1);
				start();
			} catch (Exception e) {
				throw new Error(e);
			}
		}
		private String [] line;
		private int index;
		private void newLine() {
			if (line == null || eol()) {
				line = readLine().split(" ");
				index = 0;
			}
		}
	}
	private static void print (Object o, Object... a) { printDelim(" ", o, a); }
	private static void printDelim (String delim, Object o, Object... a) { pw.println(build(delim, o, a)); }
	private static void exit (Object o, Object... a) { print(o, a); exit(); }
	private static void exit() {
		pw.close();
		System.out.flush();
		System.err.println("------------------");
		System.err.println("Time: " + ((millis() - t) / 1000.0));
		System.exit(0);
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static String build (String delim, Object o, Object... a) {
		StringBuilder b = new StringBuilder();
		append(b, o, delim);
		for (Object p : a)
			append(b, p, delim);
		return b.substring(delim.length());
	}
	private static void append(StringBuilder b, Object o, String delim) {
		if (o.getClass().isArray()) {
			int L = java.lang.reflect.Array.getLength(o);
			for (int i = 0; i < L; ++i)
				append(b, java.lang.reflect.Array.get(o, i), delim);
		} else if (o instanceof Iterable<?>)
			for (Object p : (Iterable<?>)o)
				append(b, p, delim);
		else
			b.append(delim).append(o);
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static void start() { t = millis(); }
	private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out, autoflush);
	private static long t;
	private static long millis() { return System.currentTimeMillis(); }
	public static void main (String[] args) { new B(); exit(); }
}