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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;

public class B {
    static Map<Pair, Integer> dp;
    static Map<Pair, Character> choiceMap;
    static NavigableSet<Integer>[] charLocations;
    static Pair hundred;
    static Pair longest;
    static int longestLength;
    static String s;
    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        dp = new HashMap<Pair, Integer>();
        choiceMap = new HashMap<Pair, Character>();
        s = in.nextToken();
        
        longestLength = -1;
        charLocations = (NavigableSet<Integer>[]) Array.newInstance(NavigableSet.class,26);
        for(int i = 0; i < charLocations.length; i++){
            charLocations[i] = new TreeSet<Integer>();
        }

        for(int i = 0 ; i < s.length(); i++){
            char ch = s.charAt(i);
            charLocations[ch-'a'].add(i);
        }

        hundred = null;

        for(int ch = 0; ch < 26; ch++){
            Integer left = charLocations[ch].higher(-1);
            Integer right = charLocations[ch].lower(s.length());
            if(left == null || right == null || left > right) continue;
            populate(left, right);
        }

        char[] ans;
        if(hundred == null){
            ans = new char[longestLength];
            construct(longest.i, longest.j, ans, 0 , ans.length-1);
        }else{
            ans = new char[100];
            construct(hundred.i, hundred.j, ans, 0, ans.length-1);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < ans.length; i++){
            sb.append(ans[i]);
        }
        out.println(sb.toString());

        out.close();
    }

    static void construct(int i, int j, char[] ans, int leftAns, int rightAns){
        char ch = choiceMap.get(new Pair(i,j)).charValue();
        ans[leftAns] = s.charAt(i);
        ans[rightAns] = s.charAt(j);
        leftAns++;
        rightAns--;

        if(leftAns > rightAns)return;
        Integer left = charLocations[ch-'a'].higher(i);
        Integer right = charLocations[ch-'a'].lower(j);
        construct(left, right, ans, leftAns, rightAns);
    }

    //i and j must match
    static void populate(int i, int j){
        if(hundred != null)return;
        Pair key = new Pair(i,j);
        if(!dp.containsKey(key)){
            int curMax = 0;
            int bestChar = 0;

            if(i == j){
                curMax = 1;
                bestChar = 0;
            }else if( i == j-1){
                curMax = 2;
                bestChar = 0;
            }else{
                for(int ch = 0; ch < 26; ch++){
                    Integer left = charLocations[ch].higher(i);
                    Integer right = charLocations[ch].lower(j);
                    if(left == null || right == null || left > right) continue;
                    populate(left, right);
                    if(hundred!=null)return;
                    Integer newAns = dp.get(new Pair(left, right));
                    if(2 + newAns > curMax){
                        curMax = 2 + newAns;
                        bestChar = ch;
                    }
                }
            }
            dp.put(key, curMax);
            choiceMap.put(key,  Character.valueOf((char)(bestChar + 'a')));

            if(curMax >= 100){
                hundred = key;
                return;
            }
            if(curMax > longestLength){
                longestLength = curMax;
                longest = key;
            }
        }
    }

    static class Pair{
        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + i;
            result = prime * result + j;
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Pair other = (Pair) obj;
            if (i != other.i)
                return false;
            if (j != other.j)
                return false;
            return true;
        }
        public int i;
        public int j;
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }


        public String nextToken() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}