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: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

possible=[0]*26

for i in input().strip():
    possible[ord(i)-97]+=1

# make changes
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)

# print stuff
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="")

#!/usr/bin/env python3

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 & 0x1:
                odds.append(i)
        j = 0
        for i, x in zip(range(25, -1, -1), reversed(count)):
            if x & 0x1:
                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 & 0x1:
                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


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


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 )

    #print( needChangeLetters )
    while len(needChangeLetters) >= 2:
        preIndex = needChangeLetters.popleft()
        postIndex = needChangeLetters.pop()
        counts[preIndex] += 1
        counts[postIndex] -= 1

    print( constructString( counts ) )

__starting_point()

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


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


def palindrome(s):
	chars = [0]*26
	L = len(s)
	isOdd = (L%2 != 0)
	# populate chars
	for c in s:
		n = ord(c) - 97
		chars[n] += 1
	# permutations
	
	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

	# build result
	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)


def __starting_point():
	s = input()
	result = palindrome(s)
	print(result)
__starting_point()

#!/usr/bin/env python3
# 600C_palindrom.py - Codeforces.com/problemset/problem/600/C by Sergey 2015

import unittest
import sys

###############################################################################
# Palindrom Class (Main Program)
###############################################################################


class Palindrom:
    """ Palindrom representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        self.s = uinput()

        self.cnt = [0] * 26
        for c in self.s:
            self.cnt[ord(c) - ord('a')] += 1

        self.hlen = len(self.s) // 2
        self.odd = len(self.s) % 2

        self.pcnt = list(self.cnt)
        for i in range(len(self.pcnt) - 1, -1, -1):
            if self.pcnt[i] % 2:
                self.pcnt[i] -= 1
                found = 0
                for j in range(len(self.pcnt)):
                    if self.pcnt[j] % 2:
                        self.pcnt[j] += 1
                        found = 1
                        break
                if not found:
                    self.pcnt[i] += 1

    def calculate(self):
        """ Main calcualtion function of the class """

        result = []
        mid = ""

        for (i, n) in enumerate(self.pcnt):
            if n > 0:
                c = chr(ord('a') + i)
                for i in range(n // 2):
                    result.append(c)
                if n % 2:
                    mid = c
        if self.odd:
            result += mid
            result += reversed(result[:-1])
        else:
            result += reversed(result)

        return "".join(result)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Palindrom class testing """

        # Constructor test
        test = "aabc"
        d = Palindrom(test)
        self.assertEqual(d.cnt[:3], [2, 1, 1])
        self.assertEqual(d.pcnt[:3], [2, 2, 0])

        # Sample test
        self.assertEqual(Palindrom(test).calculate(), "abba")

        # Sample test
        test = "aabcd"
        self.assertEqual(Palindrom(test).calculate(), "abcba")

        # Sample test
        test = "aabbcccdd"
        self.assertEqual(Palindrom(test).calculate(), "abcdcdcba")

        # My tests
        test = ""
        # self.assertEqual(Palindrom(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        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"

        # Run the test
        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)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Palindrom().calculate())

__starting_point()

#!/usr/bin/env python3
# 600C_palindrom.py - Codeforces.com/problemset/problem/600/C by Sergey 2015

import unittest
import sys

###############################################################################
# Palindrom Class (Main Program)
###############################################################################


class Palindrom:
    """ Palindrom representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        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):
        """ Main calcualtion function of the class """

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

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Palindrom class testing """

        # Constructor test
        test = "aabc"
        d = Palindrom(test)
        self.assertEqual(d.cnt["c"], 1)
        self.assertEqual(d.pcnt["c"], 0)

        # Sample test
        self.assertEqual(Palindrom(test).calculate(), "abba")

        # Sample test
        test = "aabcd"
        self.assertEqual(Palindrom(test).calculate(), "abcba")

        # Sample test
        test = "aabbcccdd"
        self.assertEqual(Palindrom(test).calculate(), "abcdcdcba")

        # My tests
        test = ""
        # self.assertEqual(Palindrom(test).calculate(), "0")

        # Time limit test
        # self.time_limit_test(5000)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        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"

        # Run the test
        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)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Palindrom().calculate())

__starting_point()

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

        


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)

"""
Codeforces Educational Round 2

Problem 600 C. Make Palindrome

@author yamaton
@date 2015-11-30
"""

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

from queue import Queue
import sys

def __starting_point():

    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)

__starting_point()

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 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])
#for i in range(0, d-1):
#    o1.append(ot[d-i-1])
#print(p)
#print(np)
#print(ot)
#print(ot)
#print(o)
#print(o1)
print(o+''.join(o1))


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)

# List of lowercase letters.
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')

# Constructs the alphabetically smallest palindrome based on letter frequencies for a palindrome.
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])

# Changes the counts of each letter in preparation for constructing a palindrome.
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))

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

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)


#!/usr/bin/env python3

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 list(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 list(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 list(cnt.items()))
    odd = [k for k, v in list(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)



def __starting_point():
    s = input()
    print(solve(s))

__starting_point()

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
		#print(lCounts)
		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
		#print(lCounts)
		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()
#print(makePalindrome("aaaabbbbccccddezlm"))
#print(makePalindrome(""))


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

#CF 600C isprav
q=input()
#q='aabbcccdd'

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

#print(alfavitk)
#print(first)
#print(last)


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)

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


from bisect import insort

# abcd
# aabc
# aaab aabb
# aaaa

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 list(chars.items()):
        if v%2:
            odds.append((k,v))
        else:
            evens.append((k,v))

    odds.sort()
    #print(odds)
    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()
    #print(odds,'\n', evens)

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


def __starting_point():
    main()

__starting_point()