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.

Difficulty: HARD
Tags: Dynamic programming

Constructive algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
def p2(a):
	n = len(a)
	last = [[0] * 26 for _ in range(n)]
	last[0][ord(a[0]) - 97] = 0
	for i in range(1, n):
		for j in range(26):
			last[i][j] = last[i - 1][j]
		last[i][ord(a[i]) - 97] = i
	dp = [''] * n
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, i, -1):
			k = last[j][ord(a[i]) - 97]
			if k > i:
				if k - i == 1 and len(dp[j]) < 2:
					dp[j] = a[i] + a[i]
				elif len(dp[j]) < len(dp[k - 1]) + 2:
					dp[j] = a[i] + dp[k - 1] + a[i]
					if len(dp[j]) >= 100:
						if len(dp[j]) == 101:
							return dp[j][:50] + dp[j][51:]
						else:
							return dp[j]
		dp[i] = a[i]
	return dp[n - 1]
print(p2(input()))


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:]
			elif 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]))


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