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.util.*;

public class B {

	void solve() throws IOException {
		char[] a = next().toCharArray();
		int n = a.length;
		int[][] prev = new int[26][n];
		int[] last = new int[26];
		Arrays.fill(last, -1);
		for (int i = 0; i<n; i++) {
			for (int j =0; j<26; j++) {
				prev[j][i] = last[j];
			}
			last[a[i]-'a'] = i;			
		}
		
		int[][] parent = new int[101][n];
		
		int optlen = 1;
		int optpos = 0;
		
		int[] pos0 = new int[n];
		int[] pos1 = new int[n];
		int[] pos2 = new int[n];
		for (int i = 0; i<n; i++) {
			pos0[i] = i+1;
			pos1[i] = i;
		}
		for (int it = 2; it<=100; it++) {
			int max = -1;
			int posMax = -1;
			for (int i = 0; i<n; i++) {
				if (max >= 0) {
					pos2[i] = prev[a[i]-'a'][max];
					parent[it][i] = posMax;
				} else {
					pos2[i] = -1;
				}
				if (pos2[i] != -1) {
					optlen = it;
					optpos = i;
				}
				if (pos0[i] > max) {
					max = pos0[i];
					posMax=i;
				}
			}
			for (int i = 0; i<n; i++) {
				pos0[i] = pos1[i];
				pos1[i] = pos2[i];
			}
//			if (optlen != it) {
//				break;
//			}
		}
		String res = "";
		int bestlen = optlen/2;
		while (optlen > 0) {
			res = a[optpos] + res;
			optpos = parent[optlen][optpos];
			optlen-=2;
		}
		for (int i = 0; i<bestlen; i++) {
			out.print(res.charAt(res.length()-1-i));
		}
		out.println(res);
	}

	void run() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

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

	BufferedReader br;
	PrintWriter out;
	StringTokenizer str;

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

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

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

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

}