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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStream;
import java.lang.*;

public class Source {
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter ou = new PrintWriter(System.out);		
		MainCode obj = new MainCode();
		obj.Solve(in, ou);
		ou.close();
	}
	
}

class MainCode {
	public void Solve(InputReader inp, PrintWriter out) {
		String S = inp.next();
		int n = S.length();
		
		int[][] next = new int[n + 1][26];
		for (int i = 0; i < 26; ++i) next[n][i] = n;
		for (int i = n - 1; i >= 0; --i) {
			for (int j = 0; j < 26; ++j) next[i][j] = next[i + 1][j];
			next[i][(int)S.charAt(i) - 'a'] = i;
		}
		
		int[][] dp = new int[107][n];
		for (int i = 0; i < n; ++i) dp[0][i] = i - 1;
		for (int i = 0; i < n; ++i) dp[1][i] = i;
		for (int k = 2; k <= 100; ++k) {
			dp[k][n - 1] = n;
			for (int i = n - 2; i >= 0; --i) {
				dp[k][i] = dp[k][i + 1];
				if (dp[k - 2][i + 1] < n)
					dp[k][i] = Math.min(dp[k][i], next[dp[k - 2][i + 1] + 1][(int)S.charAt(i) - 'a']);
			}
		}
		
		for (int k = 100; k >= 1; --k) {
			int p = -1;
			for (int i = 0; i < n; ++i) {
				if (dp[k][i] < n) {
					p = i;
					break;
				}
			}
			if (p == -1) continue;
			
			StringBuilder res = new StringBuilder(k);
			for (int i = 0; i < k; ++i) res.append(' ');
			for (int i = p, x = 0, y = k - 1; k > 0 && x <= y; ++i) {
				if (i == n - 1 || dp[k][i] != dp[k][i + 1]) {
					res.setCharAt(x++, S.charAt(i));
					res.setCharAt(y--, S.charAt(i));
					k -= 2;
				}
			}
			
			out.println(res.toString());
			break;
		}
	}
	
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
    
    public long nextLong() {
    	return Long.parseLong(next());
    }
    
    public double nextDouble() {
    	return Double.parseDouble(next());
    }

}