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:
import sys
import math
def II():
	return int(sys.stdin.readline())
 
def LI():
	return list(map(int, sys.stdin.readline().split()))
 
def MI():
	return map(int, sys.stdin.readline().split())
 
def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
    s = 1
    facts = [1]
    for i in range(1,n+1):
        s*=i
        s%=mod
        facts.append(s)
    return facts[n]

def C(n, k, mod):
    return (FACT(n,mod) * pow((FACT(k,mod)*FACT(n-k,mod))%mod,mod-2, mod))%mod

st = list(SI())
d = [0 for i in range(26)]
for i in range(len(st)):
    d[ord(st[i])-97]+=1
boo = False
letter = ""
for i in range(26):
    if d[i] >= 100:
        boo = True
        letter = chr(i+97)
        break
if boo:
    print("".join([letter for i in range(100)]))
else:
    rev = st[::-1]

    n = len(st)
    
    dp = [[0 for i in range(n+1)] for j in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, n+1):
            if st[i-1] == rev[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    
    ans = []
    
    i = j = n

    while i > 0 and j > 0:
        if st[i-1] == rev[j-1]:
            ans.append(st[i-1])
            i-=1
            j-=1
        elif dp[i][j-1] > dp[i-1][j]:
            j-=1
        else:
            i-=1
    if len(ans)>100:
        ans = ans[:50]+ans[-50:]
    print("".join(ans))