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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.UnsupportedEncodingException;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class B {
    private final static long START_TIME=System.currentTimeMillis();
    private final static boolean LOG_ENABLED=true;
    private final static boolean ONLINE_JUDGE = LOG_ENABLED && (System.getProperty("ONLINE_JUDGE") != null);
    private final static String SYSTEM_ENCODING="utf-8";


    private static class Logger{
        private final PrintWriter logWriter=Util.newPrintWriter(System.err,true);
        private final DecimalFormat df=new DecimalFormat("0.000");
        private void message(String type, String message, Object ... params){
            if(ONLINE_JUDGE){
                return;
            }
            logWriter.printf("["+type+"] "+df.format((System.currentTimeMillis()-START_TIME)/1000.0)+": "+message+"\r\n", params);
        }
        public void debug(String message, Object ... params){
            message("DEBUG", message, params);
        }
    }

    private final static class Util{
        public static PrintWriter newPrintWriter(OutputStream out, boolean autoFlush){
            try {
                return new PrintWriter(new OutputStreamWriter(new BufferedOutputStream(out), SYSTEM_ENCODING),autoFlush);
            } catch (UnsupportedEncodingException e) {
                throw new IllegalStateException(e);
            }
        }
    }

    public final static class FastScanner{
        private BufferedReader reader;
        private StringTokenizer currentTokenizer;
        public FastScanner(Reader reader) {
            if(reader instanceof BufferedReader){
                this.reader=(BufferedReader) reader;
            }else{
                this.reader=new BufferedReader(reader);
            }
        }

        public String next(){
            if(currentTokenizer==null || !currentTokenizer.hasMoreTokens()){
                try {
                    currentTokenizer=new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new IllegalStateException(e);
                }
            }

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

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

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

    }

    private final static Logger log=new Logger();
    private static final int RESULT_LEN = 100;
    private final BufferedReader reader;
    private final FastScanner in;
    private final PrintWriter out=Util.newPrintWriter(System.out,false);

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

    public static void main(String[] args) throws IOException {
        log.debug("Started");
        try{
            new B(new BufferedReader(new InputStreamReader(System.in, SYSTEM_ENCODING))).run();
        }finally{
            log.debug("Stopped");
        }
    }

    void run(){
        solve();
        out.flush(); 
    }

    private void solve(){
        char[] chars = in.next().toCharArray();
        int[] counts=new int[26];
        for(int i=0,n=chars.length;i<n;i++){
            if(++counts[chars[i]-'a']==RESULT_LEN){
                char[] result = new char[RESULT_LEN];
                Arrays.fill(result, chars[i]);
                printResult(result);
                return;
            }
        }
        String polindrom = findMaxPolindrom(new String(chars),RESULT_LEN);
        if(polindrom.length()>100){
            String part1 = polindrom.substring(0,50);
            String part2 = new StringBuilder(part1).reverse().toString();
            polindrom=part1+part2;
        }
        out.println(polindrom);
    }

    @SuppressWarnings("serial")
    private Map<String,String> cache=new LinkedHashMap<String, String>(1000, 0.75f, true){
        @Override
        protected boolean removeEldestEntry(Map.Entry<String,String> eldest) {
            return super.size()>60000;
        }
    };
    /**
     * @param chars
     */
    private String findMaxPolindrom(String string, int maxLen) {
        String p=cache.get(string);
        if(p!=null){
            return p;
        }
        if(string.length()<=1){
            return string;
        }
        char beginChar=string.charAt(0);
        int to = string.lastIndexOf(beginChar);
        p = findMaxPolindrom(string.substring(1), maxLen);
        if(p.length()>=maxLen){
            return p;
        }
        if(to!=0){
            String p2 = beginChar+findMaxPolindrom(string.substring(1, to),maxLen-2)+beginChar;
            if(p2.length()>p.length()){
                p=p2;
            }
        }
        cache.put(string, p);
        return p;
    }

    private void printResult(char[] result) {
        out.println(new String(result));
    }

}