A string is called palindrome if it reads the same from left to right and from right to left. For example "kazak", "oo", "r" and "mikhailrubinchikkihcniburliahkim" are palindroms, but strings "abb" and "ij" are not.

You are given string s consisting of lowercase Latin letters. At once you can choose any position in the string and change letter in that position to any other lowercase letter. So after each changing the length of the string doesn't change. At first you can change some letters in s. Then you can permute the order of letters as you want. Permutation doesn't count as changes. 

You should obtain palindrome with the minimal number of changes. If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. So firstly you should minimize the number of changes and then minimize the palindrome lexicographically.


-----Input-----

The only line contains string s (1 ≤ |s| ≤ 2·10^5) consisting of only lowercase Latin letters.


-----Output-----

Print the lexicographically smallest palindrome that can be obtained with the minimal number of changes.


-----Examples-----
Input
aabc

Output
abba

Input
aabcd

Output
abcba

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

String algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import deque

def constructString(counts):
	s = ''
	midLetter = ''
	for (i, count) in enumerate(counts):
		if count > 0:
			letter = chr(ord('a') + i)
			if count % 2 == 1:
				midLetter = letter
			s += letter * (count // 2)
	rs = s[::-1]
	return s + midLetter + rs

def __starting_point():
	counts = [0] * 26
	s = input().strip()
	n = len(s)
	for c in s:
		counts[ord(c) - ord('a')] += 1
	maxOddNum = n % 2
	curOddNum = 0
	needChangeLetters = deque()
	for (i, count) in enumerate(counts):
		if count % 2 == 1:
			needChangeLetters.append(i)
	while len(needChangeLetters) >= 2:
		preIndex = needChangeLetters.popleft()
		postIndex = needChangeLetters.pop()
		counts[preIndex] += 1
		counts[postIndex] -= 1
	print(constructString(counts))
__starting_point()


from queue import Queue
import sys
s = input()
h = set()
res = []
for x in s:
	if x in h:
		h -= {x}
		res.append(x)
	else:
		h |= {x}
odd = sorted(list(h))
for i in range(0, len(odd) // 2):
	res.append(odd[i])
if len(odd) % 2 == 1:
	mid = odd[len(odd) // 2]
else:
	mid = ''
res.sort()
ans = ''.join(res) + mid + ''.join(res[::-1])
print(ans)


import collections

def solve(s):
	n = len(s)
	chars = collections.Counter(s)
	base = sorted((c for c in chars if chars[c] >= 2 for _ in range(chars[c] // 2)))
	chars_odd = sorted((c for c in chars if chars[c] % 2 == 1))
	if n % 2 == 0:
		keep = len(chars_odd) // 2
		chars_selected = sorted(base + chars_odd[:keep])
		return chars_selected + chars_selected[::-1]
	else:
		keep = len(chars_odd) // 2
		chars_selected = sorted(base + chars_odd[:keep])
		middle = chars_odd[keep]
		return chars_selected + [middle] + chars_selected[::-1]

def main():
	s = input().strip()
	result = solve(s)
	print(''.join(result))

def __starting_point():
	main()
__starting_point()


s = input()
d = {}
for i in s:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
x = sorted(list(d.keys()))
i = 0
j = len(x) - 1
while i < j:
	if d[x[i]] % 2 != 0 and d[x[j]] % 2 != 0:
		d[x[i]] += 1
		d[x[j]] -= 1
		i += 1
		j -= 1
	elif d[x[i]] % 2 != 0:
		while d[x[j]] % 2 == 0 and j >= 0:
			j -= 1
		if j != -1:
			d[x[i]] += 1
			d[x[j]] -= 1
			i += 1
	elif d[x[j]] % 2 != 0:
		while d[x[i]] % 2 == 0 and i < len(x):
			i += 1
		if i != len(x):
			d[x[i]] += 1
			d[x[j]] -= 1
			j -= 1
	else:
		i += 1
		j -= 1
s = ''
x = ''
for i in sorted(list(d.keys())):
	if d[i] % 2 != 0:
		x = i
	s = s + i * (d[i] // 2)
print(s + x + s[::-1])


from collections import defaultdict
s = [c for c in input().strip()]
freq = defaultdict(lambda : 0)
lst = {}
for (i, c) in enumerate(s):
	lst[c] = i
	freq[c] ^= 1
skip = len(s) & 1
odds = []
for (k, v) in freq.items():
	if v == 0:
		continue
	odds.append(k)
odds.sort()
m = len(odds) >> 1
for i in range(m):
	c = odds[i]
	r = odds[len(odds) - 1 - i]
	s[lst[r]] = c
idx = defaultdict(lambda : [])
for (i, c) in enumerate(s):
	idx[c].append(i)
keys = [c for c in idx]
keys.sort()
pref = []
suff = []
mid = ''
for c in keys:
	I = idx[c]
	m = len(I) >> 1
	pref.append(c * m)
	suff.append(c * m)
	if len(I) & 1:
		mid = c
pref = ''.join(pref)
suff = ''.join(suff)
suff = suff[::-1]
print(pref + mid + suff)


import unittest
import sys

class Palindrom:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		self.s = uinput()
		self.cnt = {}
		for c in self.s:
			self.cnt[c] = self.cnt.get(c, 0) + 1
		self.odd = len(self.s) % 2
		self.pcnt = dict(self.cnt)
		for i in reversed(sorted(self.pcnt)):
			if self.pcnt[i] % 2:
				self.pcnt[i] -= 1
				found = 0
				for j in sorted(self.pcnt):
					if self.pcnt[j] % 2:
						self.pcnt[j] += 1
						found = 1
						break
				if not found:
					self.pcnt[i] += 1

	def calculate(self):
		result = []
		mid = []
		for c in sorted(self.pcnt):
			n = self.pcnt[c]
			if n > 0:
				for j in range(n // 2):
					result.append(c)
				if n % 2:
					mid.append(c)
		return ''.join(result + mid + list(reversed(result)))

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = 'aabc'
		d = Palindrom(test)
		self.assertEqual(d.cnt['c'], 1)
		self.assertEqual(d.pcnt['c'], 0)
		self.assertEqual(Palindrom(test).calculate(), 'abba')
		test = 'aabcd'
		self.assertEqual(Palindrom(test).calculate(), 'abcba')
		test = 'aabbcccdd'
		self.assertEqual(Palindrom(test).calculate(), 'abcdcdcba')
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Palindrom(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Palindrom().calculate())


S = input()
letters = {}
for i in S:
	if i not in letters:
		letters[i] = 1
	else:
		letters[i] = letters[i] + 1
used_letters = sorted(letters.keys())
num_odd = 0
used_odd = False
for i in used_letters:
	if letters[i] % 2 == 1:
		for j in used_letters[::-1]:
			if letters[j] % 2 == 1:
				letters[j] -= 1
				letters[i] += 1
				break
for i in used_letters:
	print(i * (letters[i] // 2), end='')
for i in used_letters:
	if letters[i] % 2 == 1:
		print(i, end='')
for i in used_letters[::-1]:
	print(i * (letters[i] // 2), end='')


s = input()
a = [int(i) for i in '0' * 26]
k = -1
for i in s:
	a[ord(i) - 97] += 1
for i in range(25):
	if a[i] % 2 != 0:
		for j in range(25 - i):
			if a[25 - j] % 2 != 0:
				a[i] += 1
				a[25 - j] -= 1
				break
	if a[i] % 2 != 0:
		k = i
		break
st = ''
for i in range(26):
	if a[i] > 0:
		st += chr(i + 97) * (a[i] // 2)
if k != -1:
	st = st + chr(k + 97) + st[::-1]
else:
	st = st + st[::-1]
print(st)


import sys
s = sys.stdin.readline().strip()
stats = {}
for sym in s:
	if sym not in stats:
		stats[sym] = 0
	stats[sym] += 1
sym_items = [x for (x, v) in sorted(stats.items()) if v & 1 == 1]
for (s_left, s_right) in zip(sym_items[:], sym_items[::-1]):
	if s_left == s_right or stats[s_left] & 1 == 0:
		break
	stats[s_right] -= 1
	stats[s_left] += 1
res = ''
middle_print = ''
for x in stats.keys():
	if stats[x] & 1 == 1:
		middle_print = x
		stats[x] -= 1
		break
for (x, v) in sorted(stats.items()):
	res += ''.join([x] * (v // 2))
	stats[x] -= v // 2
res += middle_print
for (x, v) in sorted(stats.items(), reverse=True):
	if v > 0:
		res += ''.join([x] * v)
print(res)


import string
s = input()
freq = {x: 0 for x in string.ascii_lowercase}
for char in s:
	freq[char] += 1
head = 'a'
tail = 'z'
while head < tail:
	if freq[tail] % 2 == 0:
		tail = chr(ord(tail) - 1)
		if tail <= head:
			break
	if freq[head] % 2 == 0:
		head = chr(ord(head) + 1)
		if tail <= head:
			break
	if freq[head] % 2 != 0 and freq[tail] % 2 != 0:
		freq[head] += 1
		freq[tail] -= 1
middle_letter = None
if head == tail and freq[head] % 2 != 0:
	middle_letter = head
	freq[head] -= 1
output = ''
for x in string.ascii_lowercase:
	for i in range(freq[x] // 2):
		output += x
if middle_letter:
	output += middle_letter + output[::-1]
else:
	output += output[::-1]
print(output)


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)

def hnbhai():
	a = list(sa())
	d = {}
	front = []
	back = []
	mid = []
	for i in a:
		d[i] = d.get(i, 0) + 1
	for i in d:
		if d[i] % 2 == 1:
			mid.append(i)
		front.extend([i] * (d[i] // 2))
		back.extend([i] * (d[i] // 2))
	mid.sort()
	while len(mid) >= 2:
		x = mid.pop(0)
		front.append(x)
		back.append(x)
		mid.pop()
	front.sort()
	back.sort(reverse=True)
	front += mid + back
	print(''.join(front))
for _ in range(1):
	hnbhai()


string = input()
occs = [0] * 26
for c in string:
	occs[ord(c) - ord('a')] += 1
mid = ''
res = list()
for idx in range(len(occs)):
	if occs[idx] & 1 == 1:
		rightmostOdd = idx
		for i in range(len(occs) - 1, idx - 1, -1):
			if occs[i] & 1 == 1:
				rightmostOdd = i
				break
		if rightmostOdd != idx:
			occs[rightmostOdd] -= 1
			occs[idx] += 1
	if occs[idx] & 1 == 1:
		mid = chr(ord('a') + idx)
	res.extend(chr(ord('a') + idx) * (occs[idx] // 2))
print(''.join(res) + mid + ''.join(reversed(res)))


import sys
input = sys.stdin.readline
s = input().rstrip()
n = len(s)
ans = [''] * n
c = {}
for i in range(n):
	c[s[i]] = c.get(s[i], 0) + 1
idx = 0
l = []
for i in range(26):
	al = chr(ord('a') + i)
	if al in c:
		while c[al] - 2 >= 0:
			ans[idx] = ans[n - 1 - idx] = al
			c[al] -= 2
			idx += 1
		if c[al] == 1:
			l.append(al)
			c[al] -= 1
l.sort(reverse=True)
while idx <= (n - 1) // 2:
	al = l.pop()
	ans[idx] = ans[n - 1 - idx] = al
	idx += 1
if n % 2 == 0:
	ans = sorted(ans[:n // 2])
	print(''.join(ans + ans[::-1]))
else:
	ans1 = sorted(ans[:n // 2])
	print(''.join(ans1 + [ans[n // 2]] + ans1[::-1]))


def main():
	wd = input()
	chars = dict()
	for c in wd:
		if c not in chars:
			chars[c] = 0
		chars[c] += 1
	odds = list()
	evens = list()
	for (k, v) in chars.items():
		if v % 2:
			odds.append((k, v))
		else:
			evens.append((k, v))
	odds.sort()
	while len(odds) > 1:
		odds[0] = (odds[0][0], odds[0][1] + 1)
		odds[-1] = (odds[-1][0], odds[-1][1] - 1)
		if odds[-1][1] < 1:
			del odds[-1]
		elif odds[-1][1] % 2 == 0:
			evens.append(odds.pop())
		if odds[0][1] % 2 == 0:
			evens.append(odds[0])
			del odds[0]
	if len(odds) and odds[0][1] > 1:
		evens.append((odds[0][0], odds[0][1] - 1))
		odds[0] = (odds[0][0], 1)
	evens.sort()
	p = list()
	for (x, c) in evens:
		for k in range(c // 2):
			p.append(x)
	if len(odds):
		print(''.join(p + [odds[0][0] for _ in range(odds[0][1])] + p[::-1]))
	else:
		print(''.join(p + p[::-1]))
main()


(s, l, p, z, x, k) = (input(), [0] * 27, 0, '', '', '')
for i in s:
	l[ord(i) - 97] += 1
for i in l:
	if i % 2:
		p += 1
p //= 2
for i in range(26, -1, -1):
	if l[i] % 2 and p:
		p -= 1
		l[i] -= 1
		for j in range(26):
			if l[j] % 2:
				l[j] += 1
				break
for j in range(26):
	o = chr(j + 97) * (l[j] // 2)
	z += o
	x = o + x
	if l[j] % 2:
		k = chr(j + 97)
print(z + k + x)


s = input()
i = 0
mp = [0 for x in range(26)]
out = ''
while i < len(s):
	mp[ord(s[i]) - ord('a')] += 1
	i += 1
front = 0
end = len(mp) - 1
while front < len(mp) and mp[front] % 2 != 1:
	front += 1
while end > 0 and mp[end] % 2 != 1:
	end -= 1
while front < end:
	mp[end] -= 1
	mp[front] += 1
	front += 1
	end -= 1
	while front < len(mp) and mp[front] % 2 != 1:
		front += 1
	while end > 0 and mp[end] % 2 != 1:
		end -= 1
out = ''
for i in range(len(mp)):
	for k in range(mp[i] // 2):
		out += chr(i + ord('a'))
rev = out[::-1]
if front < len(mp) and mp[front] % 2 == 1:
	out += chr(front + ord('a'))
print(out + rev)


def solve(s):
	cnt = dict()
	for c in s:
		if c not in cnt:
			cnt[c] = 0
		cnt[c] += 1
	num_odd = 0
	odds = []
	for (k, v) in cnt.items():
		if v % 2:
			num_odd += 1
			odds.append(k)
	odds.sort()
	for i in range(num_odd // 2):
		cnt[odds[i]] += 1
		cnt[odds[-i - 1]] -= 1
	if len(s) % 2 == 0:
		return create_palin(cnt)
	else:
		return create_palin_odd(cnt)

def create_palin(cnt):
	total = sum((v for (k, v) in cnt.items()))
	p = [None] * total
	lo = 0
	hi = total - 1
	for (k, v) in sorted(cnt.items()):
		while v > 0:
			p[lo] = k
			p[hi] = k
			lo += 1
			hi -= 1
			v -= 2
	return str.join('', p)

def create_palin_odd(cnt):
	total = sum((v for (k, v) in cnt.items()))
	odd = [k for (k, v) in cnt.items() if v % 2 == 1][0]
	p = []
	for (k, v) in sorted(cnt.items()):
		how = v // 2
		p += [k] * (v // 2)
	p = p + [odd] + list(reversed(p))
	return str.join('', p)
s = input()
print(solve(s))


s = input()
chars = [0] * 26
offset = ord('a')
for ch in s:
	chars[ord(ch) - offset] += 1
i = 0
j = 25
while i < j:
	if chars[i] % 2 == 1:
		while chars[j] % 2 == 0:
			if i >= j:
				break
			j -= 1
		else:
			chars[i] += 1
			chars[j] -= 1
	i += 1
res = ''
odd_i = -1
for i in range(26):
	if chars[i] % 2 == 1:
		odd_i = i
	res += chr(i + offset) * (chars[i] // 2)
if odd_i != -1:
	print(f'{res}{chr(odd_i + offset)}{res[::-1]}')
else:
	print(f'{res}{res[::-1]}')


text = input()
vect = [0] * 30
len_text = len(text)
for i in range(len_text):
	vect[ord(text[i]) - ord('a')] += 1
i = 0
j = 26
while i < j:
	while i < 26 and vect[i] % 2 == 0:
		i = i + 1
	while j >= 0 and vect[j] % 2 == 0:
		j = j - 1
	vect[i] += 1
	vect[j] -= 1
ch = '-'
for i in range(0, 26):
	if vect[i] % 2:
		ch = chr(i + ord('a'))
		break
rezultat = ''
for i in range(0, 26):
	for j in range(0, vect[i] // 2):
		rezultat = rezultat + chr(i + ord('a'))
print(rezultat, end='')
if ch != '-':
	print(ch, end='')
print(rezultat[::-1])


from sys import stdin
s = stdin.readline().strip()
chars = {chr(x + 97): 0 for x in range(26)}
for x in s:
	chars[x] += 1
odds = sorted([x for x in chars if chars[x] % 2 == 1])
if len(s) % 2 == 1:
	middle = odds.pop(len(odds) // 2)
	for x in range(len(odds) // 2):
		chars[odds[x]] += 1
	for x in range(len(odds) // 2, len(odds)):
		chars[odds[x]] -= 1
	newC = [(chr(x + 97), chars[chr(x + 97)]) for x in range(26)]
	newC.sort()
	s = ''
	for (c, n) in newC:
		s += c * (n // 2)
	print(s + middle + s[::-1])
else:
	for x in range(len(odds) // 2):
		chars[odds[x]] += 1
	for x in range(len(odds) // 2, len(odds)):
		chars[odds[x]] -= 1
	newC = [(chr(x + 97), chars[chr(x + 97)]) for x in range(26)]
	newC.sort()
	s = ''
	for (c, n) in newC:
		s += c * (n // 2)
	print(s + s[::-1])


from collections import Counter
s = input()
cnt = Counter(s)
cs = sorted(cnt.keys())
(i, j) = (0, len(cs) - 1)
while i < j:
	if cnt[cs[i]] % 2 == 0:
		i += 1
		continue
	if cnt[cs[j]] % 2 == 0:
		j -= 1
		continue
	cnt[cs[i]] += 1
	cnt[cs[j]] -= 1
result = ''
for c in cs:
	result += c * (cnt[c] // 2)
if cnt[cs[i]] % 2 == 1:
	print(result + cs[i] + result[::-1])
else:
	print(result + result[::-1])


s = input()
cnt = [0] * 256
for i in s:
	cnt[ord(i)] += 1
i = ord('a')
j = ord('z')
while i < j:
	while i < j and cnt[i] % 2 == 0:
		i += 1
	while i < j and cnt[j] % 2 == 0:
		j -= 1
	if i < j:
		cnt[i] += 1
		cnt[j] -= 1
		i += 1
		j -= 1
res1 = ''
res2 = ''
c = ''
for i in range(ord('a'), ord('z') + 1):
	res1 = res1 + chr(i) * (cnt[i] // 2)
	res2 = chr(i) * (cnt[i] // 2) + res2
	if cnt[i] % 2 == 1:
		c = chr(i)
print(res1 + c + res2)


import sys
import os.path
from collections import *
import math
import bisect
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
s = input().rstrip('\n')
h = Counter(s)
cnt = 0
arr = []
for i in range(97, 123):
	if h[chr(i)] % 2:
		arr.append(chr(i))
end = len(arr) - 1
start = 0
while start < end:
	h[arr[start]] += 1
	h[arr[end]] -= 1
	start += 1
	end -= 1
if start == end:
	b = arr[start]
else:
	b = ''
s = ''
for i in range(97, 123):
	s = s + chr(i) * (h[chr(i)] // 2)
print(s + b + s[::-1])


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import gcd
from math import log
from math import ceil
from math import pi
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
s = ip()
ch = [0 for i in range(26)]
for i in s:
	ch[ord(i) - 97] += 1
l = 0
h = 25
while l < h:
	while l < h and ch[l] % 2 == 0:
		l += 1
	while l < h and ch[h] % 2 == 0:
		h -= 1
	if l < h:
		ch[l] += 1
		ch[h] -= 1
		l += 1
		h -= 1
ans = ''
m = ''
for i in range(26):
	c = chr(97 + i)
	ans += c * (ch[i] // 2)
	if ch[i] % 2 == 1:
		m = c
print(ans + m + ans[::-1])


s = input()
symv = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
symdict = {}
for i in range(len(symv)):
	symdict[symv[i]] = i
word = []
for i in range(len(s)):
	if not s[i] in symv:
		symdict[s[i]] = len(symv)
		symv.append(s[i])
	word.append(symdict[s[i]])
word = sorted(word)
begin = []
end = []
usedlastsym = True
unusedsym = []
for i in range(len(word)):
	if not usedlastsym:
		if word[i - 1] == word[i]:
			begin.append(word[i])
			end.append(word[i])
			usedlastsym = True
		else:
			unusedsym.append(word[i - 1])
	else:
		usedlastsym = False
if not usedlastsym:
	unusedsym.append(word[i - 1])
while len(unusedsym) > 1:
	sym = unusedsym.pop(0)
	begin.append(sym)
	end.append(sym)
	unusedsym.pop()
begin = sorted(begin)
end = sorted(end)
if len(unusedsym) == 1:
	begin.append(unusedsym[0])
result = ''
for i in begin:
	result += symv[i]
for i in range(len(end) - 1, -1, -1):
	result += symv[end[i]]
print(result)


s = input()
a = [0] * 26
for i in s:
	a[ord(i) - 97] += 1
for i in range(26):
	if a[i] % 2:
		f = -1
		for j in range(i + 1, 26):
			if a[j] % 2:
				f = j
		if f == -1:
			break
		a[f] -= 1
		a[i] += 1
fuc = -1
for i in range(26):
	if a[i] % 2:
		fuc = i
		break
s = ''
for i in range(26):
	if a[i]:
		s += a[i] // 2 * chr(i + 97)
st = s
if fuc != -1:
	s += chr(fuc + 97)
print(s + st[::-1])


from collections import Counter
ochka = input()
otvetochka = ''
arrochka = []
lesopilochka = Counter(ochka)
s = set(ochka)
for i in s:
	if lesopilochka[i] % 2 == 0:
		otvetochka += i * (lesopilochka[i] // 2)
	else:
		arrochka.append(i)
		otvetochka += i * (lesopilochka[i] // 2)
arrochka.sort()
while len(arrochka) > 1:
	otvetochka += arrochka[0]
	arrochka.pop()
	arrochka = arrochka[1:]
if len(arrochka) == 1:
	otvetochka = ''.join(sorted(otvetochka))
	print(otvetochka + arrochka[0] + otvetochka[::-1])
	exit()
otvetochka = sorted(otvetochka)
if len(ochka) % 2 == 0:
	print(''.join(otvetochka + otvetochka[::-1]))
else:
	t = otvetochka[::-1]
	print(''.join(otvetochka + t[1:]))


from math import floor, ceil
s = input()
alph = 'abcdefghijklmnopqrstuvwxyz'
d = {}
e = set()
for x in s:
	e.add(x)
	try:
		d[x] += 1
	except:
		d[x] = 1
L = []
for x in e:
	L.append(x)
L.sort()
ch = ''.join(L)
deb = 0
fin = len(ch) - 1
while deb < fin:
	if d[ch[deb]] % 2 != 0:
		f = fin
		while deb < fin and d[ch[fin]] % 2 == 0 and (d[ch[fin]] > 0):
			fin -= 1
		if deb == fin:
			break
		d[ch[fin]] -= 1
		if d[ch[fin]] == 0:
			fin -= 1
		d[ch[deb]] += 1
	deb += 1
sol = ''
xch = ''
xx = ''
for x in ch:
	if d[x] % 2 != 0:
		xx = x
	sol += x * floor(d[x] / 2)
	d[x] -= floor(d[x] / 2)
if xx != '':
	sol += xx
	d[xx] -= 1
for x in ch[::-1]:
	sol += x * d[x]
print(sol)


s = input()
alph = [0 for x in range(0, 26)]
for i in s:
	alph[ord(i) - ord('a')] = alph[ord(i) - ord('a')] + 1
for i in range(25, -1, -1):
	if alph[i] % 2 != 0:
		for j in range(0, 26):
			if alph[j] % 2 != 0:
				alph[i] = alph[i] - 1
				alph[j] = alph[j] + 1
				break
r = ''
for i in range(0, 26):
	while alph[i] > 1:
		r = r + chr(ord('a') + i)
		alph[i] = alph[i] - 2
s = r
for i in range(0, 26):
	if alph[i] != 0:
		r = r + chr(ord('a') + i)
print(r + s[::-1])


from collections import Counter, OrderedDict
try:
	while True:
		s = input()
		count = [0] * 26
		for c in s:
			count[ord(c) - 97] += 1
		odds = []
		for (i, x) in enumerate(count):
			if x & 1:
				odds.append(i)
		j = 0
		for (i, x) in zip(range(25, -1, -1), reversed(count)):
			if x & 1:
				if i == odds[j]:
					break
				count[odds[j]] += 1
				count[i] -= 1
				j += 1
		a = []
		b = []
		c = ''
		for (i, x) in enumerate(count):
			if x & 1:
				assert not c
				c = chr(i + 97)
			if x > 1:
				t = chr(i + 97) * (x >> 1)
				a.append(t)
				b.append(t)
		print(''.join(a), ''.join(reversed(b)), sep=c)
except EOFError:
	pass


from collections import defaultdict
s = input()
l = defaultdict(int)
for c in s:
	l[c] += 1
u = sorted(list(filter(lambda x: l[x] % 2, l.keys())))
for i in range(0, int(len(u) / 2)):
	l[u[i]] += 1
	l[u[-i - 1]] -= 1
r = ''
for c in sorted(l.keys()):
	r += c * int(l[c] / 2)
c = u[int(len(u) / 2)] if len(u) % 2 else ''
print(r + c + r[::-1])


from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from sys import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer):
	stdout.write(str(answer))
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
arr = fast()
cnt = Counter(sorted(arr))
newCnt = []
for i in cnt:
	if cnt[i] % 2:
		newCnt.append(i)
l = len(newCnt)
for i in range(l // 2):
	cnt[newCnt[i]] += 1
	cnt[newCnt[l - i - 1]] -= 1
mid = newCnt[l // 2] if l % 2 else ''
ans = ''
for i in cnt:
	ans += i * (cnt[i] // 2)
print(ans + mid + ans[::-1])


iword = input().strip()
letters = {letter: iword.count(letter) for letter in set(iword)}
alph_order = 'abcdefghijklmnopqrstuvwxyz'
alph_order_back = 'zyxwvutsrqponmlkjihgfedcba'

def word(letters):
	tword = []
	middle = ''
	for letter in alph_order:
		if letter not in letters:
			continue
		if letters[letter] % 2 == 1:
			middle = letter
			letters[letter] -= 1
		if letters[letter] == 0:
			continue
		tword += [letter] * int(letters[letter] / 2)
	tword = ''.join(tword + [middle] + [tword[i] for i in range(-1, -len(tword) - 1, -1)])
	print(tword)
while True:
	mem_letter_1 = ''
	mem_letter_2 = ''
	for letter in alph_order:
		if letter not in letters:
			continue
		if letters[letter] % 2 == 1:
			mem_letter_1 = letter
			break
	if mem_letter_1 == '':
		word(letters)
		break
	for letter in alph_order_back:
		if letter not in letters:
			continue
		if letters[letter] % 2 == 1:
			mem_letter_2 = letter
			break
	if mem_letter_1 == mem_letter_2:
		word(letters)
		break
	else:
		letters[mem_letter_1] += 1
		letters[mem_letter_2] -= 1


s = str(input())
T = [0] * 26
alpha = list('abcdefghijklmnopqrstuvwxyz')
for x in s:
	T[ord(x) - 97] += 1
i = 0
while i < len(T):
	if T[i] == 0:
		del T[i]
		del alpha[i]
		i -= 1
	i += 1
j = 0
for i in range(len(T) - 1, -1, -1):
	if i <= j:
		break
	if T[i] % 2 == 0:
		continue
	else:
		while T[j] % 2 == 0:
			j += 1
			if j == i:
				break
		T[j] += 1
		T[i] -= 1
ch1 = ''
ch2 = ''
ch3 = ''
for i in range(len(T)):
	if T[i] == 0:
		continue
	else:
		ch1 = ch1 + T[i] // 2 * alpha[i]
		ch2 = T[i] // 2 * alpha[i] + ch2
	if T[i] % 2 == 1:
		ch3 += alpha[i]
print(ch1 + ch3 + ch2)


from collections import deque
s = input()
cnt = [0] * 26
for letter in s:
	cnt[ord(letter) - ord('a')] += 1
odd = []
for letter in range(26):
	if cnt[letter] % 2:
		odd.append(letter)
for i in range(len(odd) // 2):
	l_up = odd[i]
	l_down = odd[-(i + 1)]
	cnt[l_up] += 1
	cnt[l_down] -= 1
m = []
for i in range(26):
	if cnt[i] % 2:
		m.append(chr(i + ord('a')))
		cnt[i] -= 1
p = []
for i in range(26):
	while cnt[i] > 0:
		p.append(chr(i + ord('a')))
		cnt[i] -= 2
print(''.join(p) + ''.join(m) + ''.join(reversed(p)))


x = 'abcdefghijklmnopqrstuvwxyz'
d = dict.fromkeys(x, 0)
s = input()
for i in s:
	d[i] += 1
count = 0
for i in x:
	if d[i] % 2:
		count += 1
if len(s) % 2:
	count -= 1
i = len(x) - 1
while count > 0:
	if d[x[i]] % 2:
		j = 0
		while not d[x[j]] % 2:
			j += 1
		d[x[j]] += 1
		d[x[i]] -= 1
		count -= 2
	i -= 1
s = ''
flag = ''
for i in x:
	if d[i] % 2:
		flag = i
	s += i * (d[i] // 2)
print(s, flag, s[-1::-1], sep='')


s = input()
ss = dict()
for c in s:
	ss[c] = ss.get(c, 0) + 1
w = list(ss.keys())
w.sort()
wo = [a for a in w if ss[a] % 2 != 0]
for (a, b) in zip(wo[:len(wo) // 2], wo[::-1][:len(wo) // 2]):
	ss[a] += 1
	ss[b] -= 1
sr = ''.join([ss[c] // 2 * c for c in w])
p = [c for c in w if ss[c] % 2 != 0]
print(sr + ''.join(p) + sr[::-1])


inp_string = input()
LOWERCASELETTERS = 'abcdefghijklmnopqrstuvwxyz'
OCCS = {letter: 0 for letter in LOWERCASELETTERS}
for sym in inp_string:
	OCCS[sym] += 1
ODD_OCCS = [letter for letter in LOWERCASELETTERS if OCCS[letter] % 2 != 0]
N_ODD = len(ODD_OCCS)
for i in range(N_ODD // 2):
	OCCS[ODD_OCCS[i]] += 1
	OCCS[ODD_OCCS[N_ODD - 1 - i]] -= 1
ans = []
for letter in LOWERCASELETTERS:
	ans += [letter] * (OCCS[letter] // 2)
if N_ODD != 0 and OCCS[ODD_OCCS[(N_ODD - 1) // 2]] % 2 != 0:
	ans += ODD_OCCS[(N_ODD - 1) // 2]
for letter in LOWERCASELETTERS[::-1]:
	ans += [letter] * (OCCS[letter] // 2)
print(''.join(ans))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys
import math
from math import gcd
import bisect
from collections import Counter
s = input()
arr = [0] * 26
ans = ''
for i in range(len(s)):
	arr[ord(s[i]) - 97] += 1
mid = ''
odd = []
for i in range(26):
	if arr[i] % 2 != 0:
		odd.append((i, arr[i]))
odd.sort()
for i in range(len(odd) // 2):
	arr[odd[i][0]] += 1
	arr[odd[len(odd) - i - 1][0]] -= 1
for i in range(26):
	if arr[i] > 0:
		if arr[i] % 2 == 1:
			mid = chr(97 + i)
		ans += chr(i + 97) * (arr[i] // 2)
print(ans + mid + ans[::-1])


import sys
input = sys.stdin.readline
S = list(input())[:-1]
table = [0] * 26
a = ord('a')
for x in S:
	table[ord(x) - a] += 1
k = 0
for i in range(26):
	if table[i] % 2:
		k += 1
k -= len(S) % 2
for i in range(25, -1, -1):
	if k == 0:
		break
	if table[i] % 2 == 0:
		continue
	for j in range(26):
		if i == j:
			continue
		if table[j] % 2 == 0:
			continue
		table[i] -= 1
		table[j] += 1
		break
	k -= 1
res = []
for i in range(26):
	res += [chr(i + a)] * (table[i] // 2)
if len(S) % 2:
	for i in range(26):
		if table[i] % 2:
			res += [chr(i + a)] + res[::-1]
			break
else:
	res += res[::-1]
print(''.join(res))


from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def main():
	s = si()
	m = [0] * 26
	n = len(s)
	for i in range(n):
		m[ord(s[i]) - ord('a')] += 1
	i = 0
	j = 25
	f = 0
	c = -1
	while i < j:
		if f == 0:
			if m[j] % 2:
				m[j] -= 1
				c = j
				f = 1
			j -= 1
		else:
			if m[i] % 2:
				m[i] += 1
				f = 0
			i += 1
	if f == 1:
		if m[j] % 2:
			m[j] += 1
		else:
			m[c] += 1
	s1 = ''
	c = ''
	for i in range(26):
		if m[i] % 2:
			c = chr(97 + i)
			x = m[i] // 2
			s1 += chr(97 + i) * x
		else:
			x = m[i] // 2
			s1 += chr(97 + i) * x
	print(s1, end='')
	print(c, end='')
	s1 = list(s1)
	s1.reverse()
	s1 = ''.join(s1)
	print(s1)
main()


s = input()
letters = {}
for i in s:
	if i not in letters:
		letters[i] = 0
	letters[i] += 1
keylist = list(letters.keys())
keylist.sort()
uneven_list = [i for i in keylist if letters[i] % 2 != 0]
n = len(uneven_list)
for i in range(n // 2):
	letters[uneven_list[i]] += 1
	letters[uneven_list[n - i - 1]] -= 1
result = []
uneven_list = [i for i in keylist if letters[i] % 2 != 0]
for i in keylist:
	for j in range(letters[i] // 2):
		result.append(i)
if len(uneven_list) > 0:
	p = letters[uneven_list[0]]
	if len(uneven_list) == 1:
		p = p % 2
	for j in range(p):
		result.append(uneven_list[0])
for i in keylist[::-1]:
	for j in range(letters[i] // 2):
		result.append(i)
print(''.join(result))


d = [0] * 26
s = input()
n = len(s) % 2

def num2chr(x):
	return chr(x + 97)
for c in s:
	try:
		d[ord(c) - 97] += 1
	except Exception as e:
		print(c, ord(c) - 97, ord('a'))
		print(e)
i = 0
j = 25
while i < j:
	if d[i] % 2 == 0:
		i = i + 1
		continue
	if d[j] % 2 == 0:
		j = j - 1
		continue
	d[i] += 1
	d[j] -= 1
center = ''
if d[i] % 2 == 1:
	d[i] = d[i] - 1
	center = chr(i + 97)
ans = [0] * (sum(d) // 2)
i = 0
j = 0
while j < 26:
	if d[j] < 2:
		j = j + 1
		continue
	ans[i] = 97 + j
	d[j] = d[j] - 2
	i = i + 1
s = ''.join(list(map(chr, ans)))
print(s + center + s[::-1])


st = input()
arr = [0 for i in range(26)]
ch = 'a'
for i in range(26):
	arr[i] = st.count(chr(i + ord('a')))
(i, j) = (0, 25)
n = len(st)
while i < 26 and arr[i] % 2 == 0:
	i += 1
while j > 0 and arr[j] % 2 == 0:
	j -= 1
while i < j:
	arr[i] = arr[i] + 1
	arr[j] = arr[j] - 1
	while i < 26 and arr[i] % 2 == 0:
		i += 1
	while 0 < j and arr[j] % 2 == 0:
		j -= 1
r = ''
middle = ''
for i in range(26):
	c = str(chr(i + 97))
	r = r + c * (arr[i] // 2)
	if arr[i] % 2 == 1:
		middle = c
print(r + middle + r[::-1])


def create_dict(s):
	data_dict = {}
	for character in s:
		if character in data_dict:
			data_dict[character] += 1
		else:
			data_dict[character] = 1
	return data_dict

def find_unmatching(data_dict):
	unmatched = set()
	for key in data_dict:
		if data_dict[key] % 2 == 1:
			data_dict[key] -= 1
			unmatched.add(key)
	return (clear_dict(data_dict), unmatched)

def clear_dict(data_dict):
	return {key: data_dict[key] for key in data_dict if data_dict[key] > 0}

def process_unmatched(unmatched):
	sorted_unmatched = sorted(unmatched)
	to_take = []
	to_take = sorted_unmatched[:len(sorted_unmatched) // 2]
	extra = None
	if len(sorted_unmatched) % 2 == 1:
		extra = sorted_unmatched[len(sorted_unmatched) // 2]
	return (to_take, extra)

def create_palindrome(s):
	data_dict = create_dict(s)
	(new_data_dict, unmatched) = find_unmatching(data_dict)
	(to_take, extra) = process_unmatched(unmatched)
	full_list = sorted(list(new_data_dict.keys()) + to_take)
	ll = []
	for letter in full_list:
		if letter in new_data_dict:
			ll.append(letter * (data_dict[letter] // 2))
			del new_data_dict[letter]
		else:
			ll.append(letter)
	print(''.join(ll), end='')
	if extra is not None:
		print(extra, end='')
	print(''.join(reversed(ll)))
s_input = input()
create_palindrome(s_input)


import sys
from collections import Counter
from string import ascii_lowercase

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
s = input()
lowercase = ascii_lowercase
n = len(s)
freq = Counter(s)
odd = []
o = 0
for i in sorted(freq):
	if freq[i] % 2:
		odd.append(i)
		o += 1
start = 0
end = o - 1
while start < end:
	freq[odd[start]] += 1
	freq[odd[end]] -= 1
	start += 1
	end -= 1
ans = []
for i in lowercase:
	for j in range(freq[i] // 2):
		ans.append(i)
hell = ''
if n % 2:
	hell = odd[start]
print(*ans, end='', sep='')
print(hell, end='')
print(*ans[::-1], end='', sep='')


a = [0] * 26
for ch in input():
	a[ord(ch) - ord('a')] += 1
b = []
for i in range(26):
	if a[i] & 1:
		b.append(i)
(i, j) = (0, len(b) - 1)
while i < j:
	a[b[i]] += 1
	a[b[j]] -= 1
	i += 1
	j -= 1
for i in range(26):
	print(chr(ord('a') + i) * (a[i] // 2), end='')
for i in range(26):
	if a[i] & 1:
		print(chr(ord('a') + i), end='')
for i in range(25, -1, -1):
	print(chr(ord('a') + i) * (a[i] // 2), end='')


import sys
a = ord('a')
l = [0 for i in range(ord('z') - a + 1)]
x = input().rstrip()
for c in x:
	l[ord(c) - a] += 1
neparno = True if len(x) % 2 == 1 else False
neparnoindex = -1
d = 0
g = len(l) - 1
while d < g:
	if l[d] % 2 == 0:
		d += 1
		continue
	if l[g] % 2 == 0:
		g -= 1
		continue
	l[d] += 1
	l[g] -= 1
	d += 1
	g -= 1
if neparno:
	neparnoindex = d
sbuilder = ''
for i in range(len(l)):
	sbuilder += chr(a + i) * (l[i] // 2)
if neparnoindex >= 0:
	sbuilder += chr(a + neparnoindex)
for i in reversed(range(len(l))):
	sbuilder += chr(a + i) * (l[i] // 2)
print(sbuilder)


S = input()
N = len(S)
D = [0 for _ in range(26)]
for i in range(N):
	D[ord(S[i]) - 97] += 1
while True:
	odd = 0
	for i in range(26):
		if D[i] % 2 == 1:
			odd += 1
	if odd <= 1:
		break
	for i in range(26):
		if D[i] % 2 == 1:
			lt = i
			break
	for i in range(26)[::-1]:
		if D[i] % 2 == 1:
			rt = i
			break
	D[lt] += 1
	D[rt] -= 1
res = ''
for i in range(26):
	res += chr(i + 97) * (D[i] // 2)
for i in range(26):
	if D[i] % 2 == 1:
		res += chr(i + 97)
for i in range(26)[::-1]:
	res += chr(i + 97) * (D[i] // 2)
print(res)


from math import floor
s = input()
n = len(s)
ans = ['*'] * n
d = {}
e = []
o = []
for c in s:
	if c in d:
		d[c] += 1
	else:
		d[c] = 1
for k in d:
	qnt = floor(d[k] / 2)
	e += [k] * qnt
	d[k] -= qnt * 2
	if d[k]:
		o.append(k)
e.sort()
o.sort()
if len(o) % 2:
	o = o[0:floor(len(o) / 2) + 1]
else:
	o = o[0:floor(len(o) / 2)]
ans = []
if len(s) % 2:
	ans = e + o[:-1]
	ans.sort()
	ans += list(o[-1]) + ans[::-1]
else:
	ans = e + o
	ans.sort()
	ans += ans[::-1]
print(''.join(ans))


from collections import Counter, defaultdict, deque
from heapq import heapify, heappush, heappop
from bisect import bisect_left
from functools import lru_cache
import math
s = list(input())
N = len(s)
count = Counter(s)
odds = []
for (k, v) in count.items():
	if v & 1:
		odds.append(k)
odds.sort()
(lhs, rhs) = (0, len(odds) - 1)
while lhs < rhs:
	count[odds[lhs]] += 1
	count[odds[rhs]] -= 1
	(lhs, rhs) = (lhs + 1, rhs - 1)
if lhs == rhs:
	middle = odds[lhs]
	count[middle] -= 1
	middle = [middle]
else:
	middle = []
ans = []
for k in sorted(count.keys()):
	x = [k] * (count[k] // 2)
	ans.extend(x)
print(''.join(ans + middle + ans[::-1]))


a = input()
q = 'abcdefghijklmnopqrstuvwxyz'
amount = []
for i in range(len(q)):
	amount.append(0)
	amount[i] = a.count(q[i])
start = 0
end = len(amount) - 1
while start < end:
	while start < len(amount) and amount[start] % 2 == 0:
		start += 1
	while end >= 0 and amount[end] % 2 == 0:
		end -= 1
	if start < end:
		amount[start] += 1
		amount[end] -= 1
uneven = -1
for i in range(len(amount)):
	if amount[i] % 2 == 1:
		amount[i] -= 1
		uneven = i
answer = ''
for i in range(len(amount)):
	answer += q[i] * (amount[i] // 2)
	amount[i] -= amount[i] // 2
print(answer, end='')
if uneven != -1:
	print(q[uneven], end='')
print(answer[::-1])


def palindrome(s):
	chars = [0] * 26
	L = len(s)
	isOdd = L % 2 != 0
	for c in s:
		n = ord(c) - 97
		chars[n] += 1
	left = 0
	right = 25
	while left < right:
		while left < 25 and chars[left] % 2 == 0:
			left += 1
		while right > 0 and chars[right] % 2 == 0:
			right -= 1
		if left < 25 and right > 0:
			if left == right and isOdd:
				break
			else:
				chars[left] += 1
				chars[right] -= 1
	result = [' '] * L
	index = 0
	oddC = ''
	for j in range(26):
		n = chars[j]
		if n > 0:
			if n % 2 != 0:
				oddC = chr(j + 97)
			for k in range(n // 2):
				result[index] = chr(j + 97)
				result[L - 1 - index] = chr(j + 97)
				index += 1
	if isOdd:
		result[L // 2] = oddC
	return ''.join(result)
s = input()
result = palindrome(s)
print(result)


from collections import *
from math import *
s = input()
a = [0 for i in range(26)]
for i in s:
	ind = ord(i) - ord('a')
	a[ind] += 1
n = len(s)
i = 0
j = 25
while i < j:
	if a[i] % 2 == 1:
		if a[j] % 2 == 1:
			a[j] -= 1
			a[i] += 1
			j -= 1
			i += 1
		else:
			j -= 1
	else:
		i += 1
b = ['a' for i in range(n)]
f = 0
la = n - 1
for i in range(26):
	ch = chr(i + ord('a'))
	while a[i] != 0:
		if a[i] == 1:
			b[n // 2] = ch
			a[i] -= 1
		elif a[i] != 0:
			b[f] = ch
			f += 1
			b[la] = ch
			la -= 1
			a[i] -= 2
print(''.join(b))


from collections import Counter
s = Counter(sorted(list(input())))
odds = [key for key in s if s[key] % 2]
l = len(odds)
for i in range(l // 2):
	s[odds[i]] += 1
	s[odds[l - i - 1]] -= 1
mid = odds[l // 2] if l % 2 else ''
ans = ''.join([key * (s[key] // 2) for key in s])
print(ans + mid + ans[::-1])


import math as mt
import sys, string
input = sys.stdin.readline
import random
from collections import deque, defaultdict
import bisect
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
s = input().strip()
l = [0] * 26
for i in s:
	l[ord(i) - 97] += 1
c = 0
s = list(set(s))
x = []
s.sort()
for i in s:
	if l[ord(i) - 97] % 2 == 1:
		x.append(i)
k = 1
for i in range(len(x) // 2):
	if x[i] != x[-k]:
		l[ord(x[i]) - 97] += 1
		l[ord(x[-k]) - 97] -= 1
	k += 1
w = ''
q = ''
g = ''
for i in s:
	if l[ord(i) - 97] % 2 == 1:
		g = i
	w += i * (l[ord(i) - 97] // 2)
print(w + g + w[::-1])


s = input()
g = {}
for i in s:
	if g.get(i):
		g[i] += 1
	else:
		g[i] = 1
l = len(s)
while True:
	e = []
	o = []
	for i in g:
		if g[i] % 2:
			o.append(i)
		else:
			e.append(i)
	if l % 2 == len(o):
		break
	g[min(o)] += 1
	g[max(o)] -= 1
a1 = a2 = t = ''
for i in 'abcdefghijklmnopqrstuvwxyz':
	gg = g.get(i)
	if gg:
		a1 += i * (gg // 2)
		a2 = i * (gg // 2) + a2
	if gg and gg % 2 == l % 2 == 1:
		t = i
a1 += t
print(a1 + a2)


s = input()
a = [0] * 26
for c in s:
	a[ord(c) - ord('a')] += 1
x = 0
y = 25
while x < y:
	while x < y and a[x] % 2 == 0:
		x += 1
	while x < y and a[y] % 2 == 0:
		y -= 1
	if x < y:
		a[x] += 1
		a[y] -= 1
		x += 1
		y -= 1
r = ''
middle = ''
for i in range(26):
	c = str(chr(i + ord('a')))
	r += c * (a[i] // 2)
	if a[i] % 2 == 1:
		middle = c
print(r + middle + r[::-1])


from collections import Counter, OrderedDict
s = list(input())
d = Counter()
d.update(s)
d = OrderedDict(sorted(d.items(), key=lambda x: x[0]))
odds = {}
for key in d:
	if d[key] % 2:
		odds[key] = d[key]
l = len(odds)
idx = 0
for key in odds:
	if l % 2:
		if idx < l // 2:
			odds[key] += 1
			d[key] += 1
		elif idx == l // 2:
			pass
		else:
			odds[key] -= 1
			d[key] -= 1
	elif idx < l // 2:
		odds[key] += 1
		d[key] += 1
	else:
		odds[key] -= 1
		d[key] -= 1
	idx += 1
ans = ''
flag = False
c = ''
for key in d:
	if d[key] % 2:
		flag = True
		c = key
		if d[key] > 1:
			ans += key * (d[key] // 2)
	else:
		ans += key * (d[key] // 2)
if flag:
	ans += c
if len(s) % 2:
	print(ans[:len(ans) - 1] + ans[::-1])
else:
	print(ans + ans[::-1])


letters = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')

def getPalindrome(counts):
	returnString = ''
	for i in range(len(counts)):
		if counts[i] >= 2:
			for j in range(counts[i] // 2):
				counts[i] -= 2
				returnString += letters[i]
	for i in range(len(counts)):
		if counts.count(0) == 26:
			return returnString + returnString[::-1]
		elif counts[i] == 1 and counts.count(0) == 25:
			return returnString + letters[i] + returnString[::-1]

def changeCounts(counts):
	allEven = True
	for i in counts:
		if i % 2 == 1:
			allEven = False
	if allEven == True:
		return counts
	else:
		for i in range(len(counts)):
			if counts[25 - i] % 2 == 1:
				for j in range(len(counts)):
					if j == 25 - i:
						return counts
					elif counts[j] % 2 == 1:
						counts[j] += 1
						counts[25 - i] -= 1
						break
		return counts
inputArg = list(input())
counts = []
for i in letters:
	counts.append(inputArg.count(i))
counts = changeCounts(counts)
print(getPalindrome(counts))


string = input()
while not string:
	string = input()
alpha = 'abcdefghijklmnopqrstuvwxyz'
dic = {i: 0 for i in alpha}
ans = ''
for i in string:
	dic[i] += 1
dic = {i: dic[i] for i in dic if dic[i] != 0}
odd = [i for i in sorted(dic) if dic[i] % 2 != 0]
last = sorted(dic)[-1]
mid = ''
r = len(odd) - 1
l = 0
while l < r:
	dic[odd[l]] += 1
	dic[odd[r]] -= 1
	l += 1
	r -= 1
if len(odd) % 2 != 0:
	mid = odd[len(odd) // 2]
	dic[mid] -= 1
for i in sorted(dic):
	for j in range(dic[i] // 2):
		ans += i
re_ans = ans[::-1]
if mid:
	ans += mid
ans += re_ans
print(ans)


x = [c for c in input()]
x.sort()
p = len(x)
x.append('0')
k = 0
a = []
b = []
y = ['0'] * p
while k < p:
	if x[k] == x[k + 1]:
		a.append(x[k])
		k += 2
	else:
		b.append(x[k])
		k += 1
a = sorted(a + b[:len(b) // 2])
for i in range(len(a)):
	y[i] = a[i]
	y[-1 - i] = a[i]
if p % 2 == 1:
	y[(p - 1) // 2] = b[(len(b) - 1) // 2]
print(''.join(y))


s = list(input())
lens = len(s)
alphcnt = [0] * 26
for i in s:
	alphcnt[ord(i) - 97] += 1
odd = []
for i in range(26):
	if alphcnt[i] % 2 == 1:
		odd.append(i)
if lens % 2 == 1:
	odd.pop(len(odd) // 2)
lenodd = len(odd)
for i in range(lenodd // 2):
	alphcnt[odd[i]] += 1
	alphcnt[odd[lenodd - i - 1]] -= 1
ans = []
for i in range(26):
	if alphcnt[i] % 2 == 0 and alphcnt[i] > 0:
		ans.append(chr(i + 97) * (alphcnt[i] // 2))
		alphcnt[i] //= 2
	elif alphcnt[i] % 2 == 1:
		center = i
		if not alphcnt[i] == 1:
			x = alphcnt[i] // 2
			ans.append(chr(i + 97) * x)
			alphcnt[i] -= x
if lens % 2 == 1:
	ans.append(chr(center + 97))
	alphcnt[center] -= 1
for i in range(25, -1, -1):
	if alphcnt[i] > 0:
		ans.append(chr(i + 97) * alphcnt[i])
print(''.join(ans))


freq = [0] * 26
for c in input():
	freq[ord(c) - ord('a')] += 1
for i in range(26):
	if freq[i] % 2:
		for j in range(25, -1, -1):
			if freq[j] % 2:
				freq[i] += 1
				freq[j] -= 1
				break
odd = '' if sum(freq) % 2 == 0 else chr(next((i for (i, x) in enumerate(freq) if x % 2)) + ord('a'))
ans = ''.join((chr(i + ord('a')) * (x // 2) for (i, x) in enumerate(freq)))
ans = ans + odd + ans[::-1]
print(ans)


from collections import Counter
cnt = Counter(sorted(input()))
odd = [c for (c, i) in zip(cnt.keys(), cnt.values()) if i % 2]
n = len(odd)
for i in range(n // 2):
	cnt[odd[i]] += 1
	cnt[odd[n - 1 - i]] -= 1
oddc = odd[n // 2] if n % 2 else ''
ans = ''.join([c * (i // 2) for (c, i) in zip(cnt.keys(), cnt.values())])
print(ans + oddc + ans[::-1])


from collections import Counter
from math import ceil

def construct(vals: list) -> str:
	if len(vals) == 1:
		return vals[0][0] * vals[0][1]
	else:
		x = vals.pop(0)
		assert x[1] % 2 == 0
		return x[0] * (x[1] // 2) + construct(vals) + x[0] * (x[1] // 2)
s = input()
counter = Counter(s)
vals = [[k, v] for (k, v) in dict(counter).items()]
vals = sorted(vals, key=lambda x: x[0])
(ixStart, ixEnd) = (0, len(vals) - 1)
while sum((x[1] % 2 == 1 for x in vals)) > 1:
	if vals[ixStart][1] % 2 == 0:
		ixStart += 1
	elif vals[ixEnd][1] % 2 == 0:
		ixEnd -= 1
	else:
		vals[ixStart][1] += 1
		vals[ixEnd][1] -= 1
vals = list(filter(lambda x: x[1] > 0, vals))
pivot = [x[0] for x in vals if x[1] % 2 == 1]
out = ''.join((s * (x // 2) for (s, x) in vals))
out = out + ('' if len(pivot) == 0 else pivot[0]) + out[::-1]
print(out)


import sys
cc = [0] * 26
s = input()
n = len(s)
for c in s:
	cc[ord(c) - 97] += 1
odd = [i for i in range(26) if cc[i] & 1]
while len(odd) > n & 1:
	cc[odd[-1]] -= 1
	cc[odd[0]] += 1
	odd.pop()
	odd.pop(0)
ans = []
for i in range(26):
	ans.append(chr(97 + i) * (cc[i] >> 1))
ans = ''.join(ans)
mid = chr(97 + odd[0]) if odd else ''
print(ans + mid + ans[::-1])


s = input()
d = {}
for i in s:
	if i in d:
		d[i] = d[i] + 1
	else:
		d[i] = 1
l = list(d.keys())
l.sort()
a = []
b = []
for i in l:
	if d[i] > 1:
		a.append(i * (d[i] // 2))
		b.append(i * (d[i] // 2))
		d[i] = d[i] % 2
for i in sorted(list(d.keys())):
	if d[i] != 0:
		a.append(i)
b.reverse()
k = ''.join(a) + ''.join(b)
kl = list(k)
i = 0
j = len(k) - 1
while i <= j:
	if k[i] != k[j]:
		kl[j] = min(k[i], k[j])
	i = i + 1
	j = j - 1
kl.sort()
t = {}
for i in kl:
	if i in t:
		t[i] = t[i] + 1
	else:
		t[i] = 1
c = []
e = []
for i in t:
	c.append(i * (t[i] // 2))
	e.append(i * (t[i] // 2))
	t[i] = t[i] % 2
for i in t:
	if t[i] != 0:
		c.append(i)
e.reverse()
res = ''.join(c) + ''.join(e)
print(res)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	s = str(input())
	cnt = [0] * 26
	for i in range(len(s)):
		cnt[ord(s[i]) - ord('a')] += 1
	res = []
	for i in range(26):
		if cnt[i] % 2 == 1:
			res.append(i)
	for i in range(len(res) // 2):
		cnt[res[i]] += 1
		cnt[res[len(res) - i - 1]] -= 1
	ans = []
	j = -1
	for i in range(26):
		if cnt[i] > 0:
			ans += [chr(ord('a') + i)] * (cnt[i] // 2)
			cnt[i] -= 2 * (cnt[i] // 2)
			if cnt[i] > 0:
				j = i
	v = ''.join(ans)
	if j == -1:
		print(v + v[::-1])
	else:
		print(v + chr(ord('a') + j) + v[::-1])
main()


import sys
s = input().strip()
count = [0] * 26
for z in s:
	count[ord(z) - 97] += 1

def cntodd(s):
	vrni = 0
	for e in s:
		if e % 2 == 1:
			vrni += 1
	return vrni
i = len(count) - 1
j = 0
while j < i:
	if count[i] % 2 == 1:
		while count[j] % 2 != 1:
			j += 1
			if j >= i:
				break
		if j < i:
			count[i] -= 1
			count[j] += 1
		else:
			break
	i -= 1
S = ''
for i in range(len(count)):
	k = count[i]
	S += str(chr(i + 97)) * (k // 2)
for i in range(len(count)):
	if count[i] % 2 == 1:
		S = S + str(chr(i + 97)) + S[::-1]
		print(S)
		sys.exit(0)
print(S + S[::-1])


from math import floor

def main():
	s = input()
	freqs = getCharFreqs(s)
	oddFreqs = []
	for i in range(len(freqs)):
		if freqs[i] % 2 == 1:
			oddFreqs.append(chr(ord('a') + i))
	(left, right) = (0, len(oddFreqs) - 1)
	while left < right:
		freqs[ord(oddFreqs[left]) - ord('a')] += 1
		freqs[ord(oddFreqs[right]) - ord('a')] -= 1
		(left, right) = (left + 1, right - 1)
	printAsPalindrome(freqs)

def printAsPalindrome(charFreqs):
	oddIndex = printHalfGetOddIndex(charFreqs, 0, len(charFreqs), 1)
	if oddIndex != -1:
		print('{}'.format(chr(ord('a') + oddIndex)), end='')
	printHalfGetOddIndex(charFreqs, len(charFreqs) - 1, -1, -1)
	print()

def printHalfGetOddIndex(charFreqs, start, end, step):
	oddIndex = -1
	for i in range(start, end, step):
		if charFreqs[i] % 2 == 1:
			oddIndex = i
		if charFreqs[i] > 0:
			print('{}'.format(chr(ord('a') + i) * floor(charFreqs[i] / 2)), end='')
	return oddIndex

def getCharFreqs(s: str):
	freqs = [0 for i in range(26)]
	for c in s:
		freqs[ord(c) - ord('a')] += 1
	return freqs
main()


import math

def find_next(ls):
	idx = -1
	for i in range(26):
		if ls[i] % 2 != 0:
			return i
	return -1
s = input()
ls = [int(0) for i in range(26)]
for x in s:
	ls[ord(x) - 97] += 1
done = [int(0) for i in range(26)]
counter = 0
for i in range(26):
	if ls[i] % 2 == 0:
		done[i] = 1
	else:
		counter += 1
take = counter // 2 * 2
taken = 1
for i in range(25, 0, -1):
	idx = find_next(ls)
	if idx == -1:
		break
	if ls[i] % 2 != 0 and idx != i:
		ls[idx] += 1
		taken += 1
		ls[i] -= 1
	if taken == take:
		break
c = ''
for i in range(26):
	if ls[i] % 2 != 0:
		c = chr(i + 97)
		break
(start, back) = ([], [])
for i in range(26):
	ls[i] = ls[i] // 2 * 2
	for j in range(ls[i]):
		if j % 2 == 0:
			start.append(chr(i + 97))
		else:
			back.append(chr(i + 97))
back.reverse()
for x in start:
	print(x, end='')
print(c, end='')
for x in back:
	print(x, end='')


s = input()
alphabets = [chr(x) for x in range(ord('a'), ord('z') + 1)]
a = {}
for i in alphabets:
	a[i] = 0
for c in s:
	a[c] += 1
e = None
odds = [j for j in alphabets if a[j] % 2 == 1]
k = len(odds) // 2
if len(odds) % 2 == 1:
	e = odds[k]
	odds.remove(odds[k])
for j in odds[:k]:
	a[j] += 1
for j in odds[k:]:
	a[j] -= 1
v = []
for i in alphabets:
	if a[i] % 2 == 1:
		v.append(i * (a[i] // 2))
	else:
		v.append(i * (a[i] // 2))
z = ''.join(v) + (e if e is not None else '')
v.reverse()
z += ''.join(v)
print(z)


import string

def main():
	s = input()
	print(makePalindrome(s))

def makePalindrome(s):
	letters = 26
	lCounts = [0] * letters
	for c in s:
		lCounts[ord(c) - ord('a')] += 1
	odds = [i for i in range(letters) if lCounts[i] % 2 != 0]
	if len(s) % 2 == 0:
		for i in range(len(odds) // 2):
			lCounts[odds[i]] += 1
		for i in range(len(odds) // 2, len(odds)):
			lCounts[odds[i]] -= 1
		return countsToPalindrome(lCounts, 0)
	else:
		for i in range(len(odds) // 2):
			lCounts[odds[i]] += 1
		for i in range(len(odds) // 2 + 1, len(odds)):
			lCounts[odds[i]] -= 1
		return countsToPalindrome(lCounts, 0)

def countsToPalindrome(L, i, middle=''):
	if i == len(L):
		return middle
	elif L[i] % 2 == 0:
		letter = string.ascii_lowercase[i]
		return letter * (L[i] // 2) + countsToPalindrome(L, i + 1, middle) + letter * (L[i] // 2)
	else:
		letter = string.ascii_lowercase[i]
		return letter * ((L[i] - 1) // 2) + countsToPalindrome(L, i + 1, letter) + letter * ((L[i] - 1) // 2)
main()


ss = input()
a = [0] * 26
for i in ss:
	a[ord(i) - 97] += 1
i = 0
j = 25
su = ''
while i < j:
	if a[i] % 2:
		while j >= 0 and j > i:
			if a[j] % 2:
				a[i] += 1
				a[j] -= 1
				j -= 1
				break
			j -= 1
	i += 1
flag = 0
for i in range(26):
	c = a[i]
	if c % 2:
		flag = 1
		las = chr(i + 97)
	c = c // 2
	ch = chr(i + 97)
	su += ch * c
if flag:
	print(su + las + su[::-1])
else:
	print(su + su[::-1])


from collections import Counter

def main():
	alphabet = 'abcdefghijklmnopqrstuvwxyz'
	s = input()
	n = len(s)
	freq = Counter(s)
	odds = []
	for c in alphabet:
		if freq[c] % 2 == 1:
			odds.append(c)
	start = 0
	end = len(odds) - 1
	while start < end:
		freq[odds[start]] += 1
		freq[odds[end]] -= 1
		start += 1
		end -= 1
	out = []
	for c in alphabet:
		for _ in range(freq[c] // 2):
			out.append(c)
	if n % 2 == 1:
		out.append(odds[start])
	for c in reversed(alphabet):
		for _ in range(freq[c] // 2):
			out.append(c)
	print(''.join(out))
main()


s = input()
n = len(s)
d = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
ltype = set()
for i in s:
	d[i] += 1
	ltype.add(i)
if n % 2 == 0:
	oddPos = []
	oddNum = 0
	for i in range(97, 123):
		if d[chr(i)] % 2 == 1:
			d[chr(i)] -= 1
			oddNum += 1
			oddPos.append(chr(i))
	oddNum //= 2
	for i in range(oddNum):
		d[oddPos[i]] += 2
	for i in range(97, 123):
		print(chr(i) * (d[chr(i)] // 2), end='')
		d[chr(i)] //= 2
	for i in range(122, 96, -1):
		print(chr(i) * d[chr(i)], end='')
else:
	lnum = len(ltype)
	oddPos = []
	oddNum = 0
	for i in range(97, 123):
		if d[chr(i)] % 2 == 1:
			d[chr(i)] -= 1
			oddNum += 1
			oddPos.append(chr(i))
	oddNum = (oddNum + 1) // 2
	for i in range(oddNum - 1):
		d[oddPos[i]] += 2
	for i in range(97, 123):
		d[chr(i)] -= d[chr(i)] // 2
		print(chr(i) * d[chr(i)], end='')
	print(oddPos[oddNum - 1], end='')
	for i in range(122, 96, -1):
		print(chr(i) * d[chr(i)], end='')


s = input()
count = [0] * 26
for i in s:
	count[ord(i) - ord('a')] += 1
ind = []
for i in range(26):
	if count[i] % 2:
		ind.append(i)
i = 0
j = len(ind) - 1
while j - i > 0:
	count[ind[i]] += 1
	count[ind[j]] -= 1
	i += 1
	j -= 1
s = ''
j = -1
for i in range(26):
	if count[i] % 2:
		j = i
	s += chr(i + 97) * (count[i] // 2)
ss = s[::-1]
if j != -1:
	s += chr(j + 97)
s += ss
print(s)


from collections import defaultdict
import sys

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]

def main():
	s = input()
	d = defaultdict(int)
	for char in s:
		d[char] += 1
	if len(s) % 2 == 0:
		V = []
		for (key, value) in d.items():
			if value % 2 != 0:
				value -= 1
				V.append(key)
		V.sort()
		assert len(V) % 2 == 0
		for char in V[:len(V) // 2]:
			d[char] += 1
		for char in V[len(V) // 2:]:
			d[char] -= 1
		half = []
		for (key, value) in d.items():
			for i in range(value // 2):
				half.append(key)
		half.sort()
		half = ''.join(half)
		print(half + half[::-1])
	else:
		V = []
		for (key, value) in d.items():
			if value % 2 != 0:
				V.append(key)
		V.sort()
		for char in V[:len(V) // 2]:
			d[char] += 1
		for i in range(1, len(V) // 2 + 1):
			d[V[-i]] -= 1
		middle = ''
		half = []
		for (key, value) in d.items():
			if value % 2 != 0:
				d[key] -= 1
				middle = key
				for i in range(d[key] // 2):
					half.append(key)
			else:
				for i in range(value // 2):
					half.append(key)
		half.sort()
		half = ''.join(half)
		print(half + middle + half[::-1])
	return 0
main()


s = str(input())
d = dict()
for el in range(97, 97 + 26):
	d[chr(el)] = 0
for el in s:
	d[el] += 1
c = 0
for el in d:
	if d[el] % 2 == 1:
		c += 1
pari = c % 2 == 0
c = c // 2
for el in sorted(d.keys()):
	if d[el] % 2 == 1:
		if c > 0:
			d[el] += 1
		elif c == 0 and (not pari):
			charspecial = el
			d[el] -= 1
		else:
			d[el] -= 1
		c -= 1
res = ''
for el in d:
	res += d[el] // 2 * el
if pari:
	print(res + res[::-1])
else:
	print(res + charspecial + res[::-1])


import sys
input = sys.stdin.readline
possible = [0] * 26
for i in input().strip():
	possible[ord(i) - 97] += 1
temp = []
for i in range(26):
	if possible[i] % 2:
		temp.append(i)
while len(temp) > 1:
	possible[temp[0]] += 1
	possible[temp[-1]] -= 1
	temp.pop(0)
	temp.pop(-1)
for i in range(26):
	print(chr(97 + i) * (possible[i] // 2), end='')
if temp:
	print(chr(97 + temp[0]), end='')
for i in range(26)[::-1]:
	print(chr(97 + i) * (possible[i] // 2), end='')


s = input()
d = {}
for x in s:
	if not x in d:
		d[x] = 1
	else:
		d[x] += 1
a = []
b = []
for x in sorted(d):
	if d[x] % 2 == 1:
		b.append([x, d[x]])
	else:
		a.append([x, d[x]])
l = len(b)
for i in range(l // 2):
	b[i][1] += 1
	b[l - i - 1][1] -= 1
	if b[l - i - 1][1] == 0:
		del b[l - i - 1]
a = a + b
a.sort()
s = ''
x = ''
for i in range(len(a)):
	s += a[i][0] * (a[i][1] // 2)
	if a[i][1] % 2 == 1:
		x = a[i][0]
print(s + x + s[::-1])


import random

def generate_test():
	alphabet = [str(x) for x in 'abcdefghijklmnopqrstuvwxyz']
	string = ''
	for i in range(50):
		n = random.randint(0, 25)
		string += alphabet[n]
	return string

def count_letters(string):
	freqs = list([0] * 26)
	length = 0
	for letter in string:
		i = ord(letter) - 97
		freqs[i] += 1
		length += 1
	return (length, freqs)

def count_odd(freqs):
	odds = 0
	for number in freqs:
		if number % 2 == 1:
			odds += 1
	return odds

def make_palindrome(freqs):
	alphabet = [str(x) for x in 'abcdefghijklmnopqrstuvwxyz']
	answer = ''
	for (index, number) in enumerate(freqs):
		if number % 2 == 1:
			freqs[index] -= 1
			answer = alphabet[index]
	while freqs:
		cur_letter = alphabet.pop()
		f = freqs.pop()
		answer = cur_letter * (f // 2) + answer + cur_letter * (f // 2)
	return answer

def solve():
	string = str(input())
	(n, freqs) = count_letters(string)
	odds = count_odd(freqs) // 2
	(count, cur) = (0, 0)
	while count < odds:
		cur_freq = freqs[cur]
		if cur_freq % 2 == 1:
			freqs[cur] += 1
			count += 1
		cur += 1
	(count, cur) = (0, 25)
	while count < odds:
		cur_freq = freqs[cur]
		if cur_freq % 2 == 1:
			freqs[cur] -= 1
			count += 1
		cur -= 1
	return make_palindrome(freqs)
print(solve())


key = ''
ok = []
odd = []
x = list(input())
d = {}
for i in 'abcdefghijklmnopqrstuvwxyz':
	d[i] = 0
for i in x:
	d[i] += 1
for i in 'abcdefghijklmnopqrstuvwxyz':
	if d[i] % 2 == 1:
		odd.append(i)
odd.sort()
m = len(odd) // 2
for i in range(len(odd[m:])):
	d[odd[i]] += 1
	d[odd[m:][i]] -= 1
for i in 'abcdefghijklmnopqrstuvwxyz':
	if d[i] % 2 == 1:
		key = i
s = ''
for i in 'abcdefghijklmnopqrstuvwxyz':
	s += i * (d[i] // 2)
print(s + key + s[::-1])


import math
s1 = input()
s1 = ''.join(sorted(s1))
nen = 0
p = ''
np = ''
ot = ''
o = ''
i = 0
o1 = []
while i < len(s1):
	if i == len(s1) - 1:
		np = np + s1[i]
	elif s1[i] == s1[i + 1]:
		p = p + s1[i]
		i = i + 1
	else:
		np = np + s1[i]
	i = i + 1
d = math.ceil(len(s1) / 2)
if len(s1) % 2 == 0:
	ot = ot + p
	for i in range(0, int(len(s1) / 2) - len(p)):
		ot = ot + np[i]
	ot = ''.join(sorted(ot))
else:
	ot = ot + p
	for i in range(0, int(math.ceil(len(s1) / 2)) - 1 - len(p)):
		ot = ot + np[i]
		nen = i + 1
	ot = ''.join(sorted(ot))
	ot = ot + np[nen]
for i in range(0, d):
	o = o + ot[i]
if len(s1) % 2 == 0:
	for i in range(0, d):
		o1.append(ot[d - i - 1])
else:
	for i in range(0, d - 1):
		o1.append(ot[d - i - 2])
print(o + ''.join(o1))


import sys
s = list(input())
s.sort()
first = []
funused = ''
unused = []
i = 1
while i < len(s):
	if s[i - 1] == s[i]:
		first.append(s[i - 1])
		s[i] = '#'
		i += 1
	else:
		if len(funused) == 0:
			funused = s[i - 1]
		unused += s[i - 1]
	i += 1
if i == len(s):
	if len(funused) == 0:
		funused = s[i - 1]
	unused += s[i - 1]
ans = first
if len(s) % 2 == 1:
	l = len(s) // 2 - len(ans)
	ans += unused[:len(s) // 2 - len(ans)]
	ans.sort()
	funused = unused[l]
	ans += [funused] + ans[::-1]
else:
	ans += unused[:len(s) // 2 - len(ans)]
	ans.sort()
	ans += ans[::-1]
print(''.join(ans))


a = input()
n = len(a)
b = [0] * 26
for i in a:
	b[ord(i) - 97] += 1
c = []
for i in range(26):
	if b[i] % 2 == 1:
		c.append(i)
k = len(c)
p = k // 2
ans = ''
for i in range(p):
	f = c[i]
	l = c[k - i - 1]
	b[f] += 1
	b[l] -= 1
for i in range(26):
	for j in range(b[i] // 2):
		ans += chr(i + 97)
print(ans, end='')
if n % 2 == 1:
	print(chr(c[k // 2] + 97), end='')
ans1 = ans[::-1]
print(ans1)


q = input()
alfavitk = [0] * 26
alfavit = 'abcdefghijklmnopqrstuvwxyz'
for i in range(26):
	alfavitk[i] = q.count(alfavit[i])
first = 0
last = 25
while True:
	while alfavitk[first] % 2 == 0 and first < last:
		first += 1
	while alfavitk[last] % 2 == 0 and first < last:
		last -= 1
	if first < last:
		alfavitk[first] += 1
		alfavitk[last] -= 1
		first += 1
		last -= 1
	else:
		break
if alfavitk[first] % 2 == 1:
	res = alfavit[first]
	alfavitk[first] -= 1
else:
	res = ''
for i in range(25, -1, -1):
	if alfavitk[i] % 2 == 1:
		res = alfavit[i] * ()
	res = alfavit[i] * (alfavitk[i] // 2) + res + alfavit[i] * (alfavitk[i] // 2)
print(res)