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:
//package cf194;

import java.util.*;
import java.io.*;

public class B2 {
	Scanner in;
	PrintWriter out;
	int[][] d ;
	int[][] pl ;
	int[][] pr ;
	String s;
	public void solve() throws IOException {
		s = in.next();
		final int k = 300;
		int n = s.length();
		int[] cnt = new int[k];
		for (int i = 0; i < n; i++) {
			cnt[s.charAt(i)]++;
		}
		for (int i = 0; i < k; i++) {
			if (cnt[i] >= 100) {
				for (int j = 0; j < 100; j++) {
					System.out.print(Character.toChars(i));
				}
				return;
			}
		}
		d = new int[n][n];
		pl = new int[n][n];
		pr = new int[n][n];
		for (int len = 0; len < n; len++) {
			for (int left = 0; left < n - len; left++) {
				int right = len + left;
				if (s.charAt(right) == s.charAt(left)) {
					if (left == right) {
						d[left][right] = 1;
					} else {
						d[left][right] = d[left + 1][right - 1] + 2;
					}
					pl[left][right] =  left + 1;
					pr[left][right] =  right - 1;
				} else {
					if (d[left + 1][right] >= d[left][right - 1]) {
						d[left][right] = d[left + 1][right];
						pl[left][right] =  left + 1;
						pr[left][right] =  right;
					} else {
						d[left][right] = d[left][right - 1];
						pl[left][right] =  left;
						pr[left][right] =  right - 1;
					}
				}
			}
		}
		String ans = getAns(0, n - 1);
		//System.out.println(ans);
		//System.out.println("Im here");
		if (ans.length() > 100) {
			int d = ans.length() - 100;
			ans = ans.substring(d / 2, ans.length() - d / 2);
			//System.out.println("Im here 2");
			if (d % 2 != 0) {
				for (int i = 0; i < ans.length(); i++) {
					//System.out.println("Im here 3");
					if (i != ans.length() / 2) {
						System.out.print(ans.charAt(i));
					}
				}
				return;
			} 
		}
		//System.out.println("Im here 4");
		System.out.print(ans);
	}

	private String getAns(int i, int j) {
		if (i > j) {
			return new String();
		}
		if (i == j) {
			return  Character.toString(s.charAt(i));
		}
		if ((pl[i][j] == i + 1) && (pr[i][j] == j - 1)) {
			return s.charAt(i) + getAns(i + 1, j - 1) + s.charAt(j);
		} else { 
			return getAns(pl[i][j], pr[i][j]);
		}
	}

	public void run() {
		try {
			in = new Scanner(System.in);
			out = new PrintWriter(System.out);

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

	public static void main(String[] arg) {
		new B2().run();
	}
}