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 PYTHON3):

Solution:
from collections import defaultdict

s = input()
n = len(s)

if n >= 2600:
    print(s[0] * 100)
elif n > 2574:
    count = defaultdict(int)
    for l in s:
        count[l] += 1
    max_l = s[0]
    for l, c in count.items():
        if c >= 100:
            max_l = l
    print(max_l * 100)

else:
    data = defaultdict(dict)
    
    def print_p(i, gap):
        if gap == 1:
            return s[i]
        if gap == 2:
            return s[i:i + 2]
        return s[i] + print_p(data[i + 1][gap - 2][1], data[i + 1][gap - 2][2]) + s[i]
    
    for i in range(n):
        data[i][1] = (1, i, 1)
    max_p = data[0][1]
    
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            data[i][2] = (2, i, 2)
            max_p = data[i][2]
        else:
            data[i][2] = data[i][1]
    
    output = None
    for gap in range(3, n + 1):
        for i in range(n - gap + 1):
            j = i + gap - 1
            if s[i] == s[j]:
                size = data[i + 1][gap - 2][0] + 2
                data[i][gap] = (size, i, gap)
                if size > max_p[0]:
                    max_p = data[i][gap]
                if size == 100:
                    output = print_p(i, gap)
                if size == 101:
                    output = print_p(i, gap)
                    output = output[:50] + output[51:]
            else:
                if data[i][gap - 1][0] > data[i + 1][gap - 1][0]:
                    data[i][gap] = data[i][gap - 1]
                else:
                    data[i][gap] = data[i + 1][gap - 1]
    if output:
        print(output) 
    else:
        print(print_p(max_p[1], max_p[2]))