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

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	public void solve() throws Throwable {
		char s [] = in.readLine().toCharArray();
		int n = s.length;
		int next [][] = new int [n][26];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 26; j++) {
				next[i][j] = -1;
			}
		}
		for (int i = 0; i < n; i++) {
			if (i > 0)
				for (int j = 0; j < 26; j++)
					next[i][j] = next[i - 1][j];
			next[i][s[i] - 'a'] = i;
		}
		int dp [][] = new int [n + 1][101];
		int p [][] = new int [n + 1][101];
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= 100; j++) {
				dp[i][j] = -5;
				p[i][j] = -1;
			}
		}
		dp[0][0] = n - 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= 100; j++) {
				if (dp[i][j] >= 0) {
					// pass
					if (dp[i + 1][j] < dp[i][j]) {
						dp[i + 1][j] = dp[i][j];
						p[i + 1][j] = 0;
					}
					// get
					int index = dp[i][j];
					if (next[index][s[i] - 'a'] >= i) {
						if (next[index][s[i] - 'a'] == i) {
							if (j + 1 <= 100) {
								if (dp[i + 1][j + 1] < next[index][s[i] - 'a'] - 1) {
									dp[i + 1][j + 1] = next[index][s[i] - 'a'] - 1;
									p[i + 1][j + 1] = 1;
								}
							}
						} else {
							if (j + 2 <= 100) {
								if (dp[i + 1][j + 2] < next[index][s[i] - 'a'] - 1) {
									dp[i + 1][j + 2] = next[index][s[i] - 'a'] - 1;
									p[i + 1][j + 2] = 2;
								}
							}
						}
					}
				}
			}
		}
		StringBuilder ans = new StringBuilder();
		char c = 'A';
		int maxLen = 0;
		int k = -1;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= 100; j++)
				if (dp[i][j] != -5) {
					if (j > maxLen) {
						maxLen = j;
						k = i;
					}
				}
		while (k >= 0) {
			int add = p[k][maxLen];
			if (add == 1) {
				c = s[k - 1];
				maxLen--;
			} else if (add == 2) {
				ans.append(s[k - 1]);
				maxLen -= 2;
			}
			k--;
		}
		out.print(ans.reverse().toString());
		if (c != 'A')
			out.print(c);
		out.println(ans.reverse().toString());
	}
	

	static Throwable t;

	BufferedReader in;
	FastScanner sc;
	PrintWriter out;

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Solution.t = t;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread thread = new Thread(null, new Solution(), "", 1 << 26);
		thread.start();
		thread.join();
		if (Solution.t != null)
			throw t;
	}

}

class FastScanner {

	BufferedReader in;
	StringTokenizer st;

	public FastScanner(BufferedReader in) {
		this.in = in;
	}

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

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

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

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

}