Kolya has a string s of length n consisting of lowercase and uppercase Latin letters and digits.

He wants to rearrange the symbols in s and cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as madam or racecar.

Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 4·10^5) — the length of string s.

The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.


-----Output-----

Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.

Print to the second line k strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length.


-----Examples-----
Input
6
aabaac

Output
2
aba aca 
Input
8
0rTrT022

Output
1
02TrrT20 
Input
2
aA

Output
2
a A

Difficulty: competition

Starter code:

Solutions:
#!/usr/bin/env python3

def main():
    import collections

    n = int(input())
    s = input()
    alph = collections.Counter(s)
    odd = sum(x & 0x1 for x in alph.values())
    dq = collections.deque()
    if odd == 0:
        print(1)
        for c, x in alph.items():
            dq.append(c * (x >> 1))
            dq.appendleft(c * (x >> 1))
        print(*dq, sep="")
    else:
        for odd in range(odd, n):
            if (n - odd) % (odd << 1) == 0:
                print(odd)
                odds = [c for c, x in alph.items() if x & 0x1]
                items = list(alph.items())
                while len(odds) != odd:
                    for i, x in enumerate(items):
                        if x[1] > 1:
                            items[i] = (x[0], x[1] - 2)
                            odds.append(x[0])
                            odds.append(x[0])
                            break
                req_length = (n - odd) // odd + 1
                cur_length = 0
                while odd > 0:
                    if cur_length == 0:
                        dq.append(odds[-1])
                        cur_length += 1
                        odds.pop()
                    x = min(items[-1][1] >> 1, (req_length - cur_length) >> 1)
                    dq.append(items[-1][0] * x)
                    dq.appendleft(items[-1][0] * x)
                    cur_length += x << 1
                    if items[-1][1] - (x << 1) <= 1:
                        items.pop()
                    else:
                        items[-1] = (items[-1][0], items[-1][1] - (x << 1))
                    if cur_length == req_length:
                        print(*dq, sep="", end=' ')
                        odd -= 1
                        dq.clear()
                        cur_length = 0
                print()
                break
        else:
            print(n)
            print(*s)

try:
    while True:
        main()
except EOFError:
    pass


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/10/22 18:15

"""

N = int(input())
S = input()

def split(s, wc, pl, n):

    ans = []

    if pl % 2 == 0:
        if any([x % 2 == 1 for x in list(wc.values())]):
            return []
        for i in range(0, len(s), pl):
            t = s[i:i + pl]
            ans.append(t[::2] + t[::-1][::2])

        return ans

    mid = [w for w, c in list(wc.items()) if c % 2 == 1]

    if len(mid) > n:
        return []

    midindex = 0
    while len(ans) < n:
        t = ''
        u = mid[midindex] if midindex < len(mid) else ''
        midindex += 1
        if not u:
            u = list([w for w, c in list(wc.items()) if c > 0])[0]
        wc[u] -= 1

        need = pl-1
        while need > 0:
            pneed = need
            for w, c in [(w, c) for w, c in list(wc.items())]:
                if c > need:
                    t += str(w) * (need//2)
                    wc[w] -= need
                    need = 0
                    break
                elif c > 1:
                    c //= 2
                    t += str(w) * c
                    wc[w] -= c * 2
                    need -= c*2
            if need == pneed:
                return []
        t = t + u + t[::-1]
        if len(t) < pl:
            return []
        ans.append(t)

    return ans




S = "".join(sorted(list(S)))
WC = collections.Counter(S)

for parts in range(1, N+1):
    if N % parts == 0:
        wc = {k: v for k, v in list(WC.items())}
        ans = split(S, wc, N//parts, parts)
        if ans:
            print(parts)
            print(" ".join(ans))
            return


from collections import Counter
n = int(input())
cnt = Counter(input())
odd = []
even = []
for s, c in cnt.items():
  if c % 2 == 1:
    odd.append([s, c])
  else:
    even.append([s, c])
k = max(1, len(odd))
for i in range(k, n + 1):
  h = n // i
  if i * h == n and (not odd and h % 2 == 0 or odd and h % 2 == 1):
    k = i
    break
h = n // k
res = []
while len(res) < k:
  if odd:
    s, c = odd.pop()
    res.append(s)
    c -= 1
    if c:
      even.append([s, c])
  elif h % 2:
    res.append(even[0][0])
    res.append(even[0][0])
    even[0][1] -= 2
    if not even[0][1]:
      even.pop(0)
  else:
    res.append('')
for i in range(k):
  s = res[i]
  while len(s) < h:
    t = (h - len(s)) // 2
    a, c = even[0]
    if c <= 2 * t:
      c //= 2
      s = a*c + s + a*c
      even.pop(0)
    else:
      s = a*t + s + a*t
      even[0][1] -= 2 * t
  res[i] = s

print(len(res))
print(' '.join(res))

n = int(input())
string = input()
char = []
charPair = []
charImpair = []
for car in string:
	if car not in char:
		z = string.count(car)
		while z>1:
			charPair.append(car)
			z-=2
		if(z==1):
			charImpair.append(car)
		char.append(car)
if len(charImpair) ==0 :
	String1 = ''
	for x in charPair:
		String1+= x
	if len(charImpair) ==1 :
		String1 += charImpair[0]
	for x in charPair[::-1]:
		String1 += x
	print('1')
	print(String1)
else :
	nbPalin = len(charImpair)
	while len(charPair)%nbPalin != 0 : 
		nbPalin += 2
		charImpair.append(charPair[-1])
		charImpair.append(charPair[-1])
		del(charPair[-1])
	lenPalindrome = n/nbPalin
	Palin = []
	for i in range(nbPalin):
		String2 = ''
		indice = i * int(((lenPalindrome-1)/2))
		for x in charPair[indice : int(indice + ((lenPalindrome-1)/2))]:
			String2 += x
		String2 += charImpair[i]
		for x in range(indice + int(((lenPalindrome-1)/2))-1, indice-1 ,-1):   #   charPair[i + int(((lenPalindrome-1)/2))-1: i-1 :-1]:
			String2 += charPair[x]	
		Palin.append(String2)
		
	print(nbPalin)
	String3 = ' '.join(Palin)
	print(String3)



n = int(input())
s = input()
d = {}
for c in s:
    if c not in d:
        d[c] = 0
    d[c] += 1
odd = []
sum = 0
for key in d:
    if d[key] % 2 == 1:
        odd.append(key)
        d[key] -= 1
    sum += d[key]

if sum // 2 < len(odd):
    print(len(s))
    for c in s:
        print(c+' ', end='')
    return
while True:
    if len(odd) == 0 or (sum // 2) % len(odd) == 0:
        break
    sum -= 2
    if sum // 2 < len(odd):
        print(len(s))
        for c in s:
            print(c + ' ', end='')
        return
    for key in d:
        odd.append(key)
        odd.append(key)
        d[key] -= 2
        if d[key] == 0:
            d.pop(key, None)
        break
if len(odd) == 0:
    odd.append('')
even = []
for key in d:
    even += [key] * (d[key] // 2)
l = (sum // 2) // len(odd)
print(len(odd))
for i in range(len(odd)):
    s = odd[i]
    for j in range(i * l, (i + 1) * l):
        s = even[j] + s + even[j]
    print(s + ' ', end='')


from collections import Counter

n = int(input())
inp = input()

c = Counter(inp)

t = len(list([x for x in list(c.values()) if x % 2 == 1]))

if t == 0:
    temp = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])

    print(1)
    print(''.join(temp) + ''.join(temp[::-1]))

else:
    ones = list()
    for j in range(len(list(c.items()))):
        i = list(c.items())[j]
        if i[1] % 2 == 1:
            c[list(c.keys())[j]] -= 1
            ones.append(i[0])

    others = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])

    while n % t != 0 or n // t % 2 == 0:
        t += 2
        o = others.pop()
        ones.append(o)
        ones.append(o)
    L = n // t

    ans = list()
    ot = 0
    for i in range(t):
        mid = str()
        if L % 2 == 1:
            mid = ones[i]
        ln = L // 2
        ans.append(''.join(others[ot: ot + ln]) + mid + ''.join(others[ot: ot + ln][::-1]))
        ot += ln


    print(t)
    print(' '.join(ans))


from collections import Counter

n = int(input())
inp = input()

c = Counter(inp)

t = len(list([x for x in list(c.values()) if x % 2 == 1]))

if t == 0:
    temp = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])

    print(1)
    print(''.join(temp) + ''.join(temp[::-1]))

else:
    ones = list()
    for j in range(len(list(c.items()))):
        i = list(c.items())[j]
        if i[1] % 2 == 1:
            c[list(c.keys())[j]] -= 1
            ones.append(i[0])

    others = sum([[list(c.items())[j][0]] * (list(c.items())[j][1] // 2) for j in range(len(list(c.items())))], [])

    while n % t != 0 or n // t % 2 == 0:
        t += 2
        o = others.pop()
        ones.append(o)
        ones.append(o)
    L = n // t

    ans = list()
    ot = 0
    for i in range(t):
        mid = str()
        if L % 2 == 1:
            mid = ones[i]
        ln = L // 2
        ans.append(''.join(others[ot: ot + ln]) + mid + ''.join(others[ot: ot + ln][::-1]))
        ot += ln


    print(t)
    print(' '.join(ans))


import sys
from collections import Counter


def gen(counter, skip):
    for c, n in counter:
        has = n // 2
        if skip > has:
            skip -= has
            has = 0
        elif skip > 0:
            has -= skip
            skip = 0
        for i in range(has):
            yield c


def gen_o(counter, take):
    for c, n in counter:
        for i in range(n % 2):
            yield c
    for c, n in counter:
        has = (n // 2) * 2
        if take > has:
            take -= has
        elif take > 0:
            has = take
            take = 0
        for i in range(has):
            yield c


N = int(next(sys.stdin))

s = next(sys.stdin).strip()
c = Counter(s)

even = 0
odd = 0
items = list(c.items())
for _, n in items:
    even += n // 2
    odd += n % 2
generator = gen(items, 0)
generator_o = gen_o(items, 0)

odd_c = odd
if odd == 0:
    print(1)
    front = [next(generator) for i in range(len(s) // 2)]
    fs = "".join(front)
    print(fs + fs[::-1])
else:
    skip = 0
    while even != 0 and even % odd != 0:
        skip += 1
        odd += 2
        even -= 1
    generator = gen(items, skip)
    generator_o = gen_o(items, skip * 2)
    print(odd)
    per = even // odd
    strs = []
    for i in range(odd):
        front = [next(generator) for i in range(per)]
        fs = "".join(front)
        strs.append(fs + next(generator_o) + fs[::-1])
    print(" ".join(strs))


n = int(input())
s = list(input())
d = {}
for char in s:
    if char not in list(d.keys()):
        d[char] = 1
    else:
        d[char] += 1

odd = []
even = []
for char in list(d.keys()):
    for i in range(d[char] // 2):
        even.append(char)
        even.append(char)
    for i in range(d[char] % 2):
        odd.append(char)
# print(len(even), len(odd))
if len(odd) <= 1:
    x = ''.join([even[i] for i in range(1, len(even), 2)])
    y = ''.join(odd)
    print(1)
    print(x + y + x[::-1])
elif len(even) % len(odd) == 0 and (len(even) // len(odd)) % 2 == 0 and (len(even) // len(odd)) > 0:
    print(len(odd))
    x = []
    ratio = len(even) // len(odd)
    indx = 0
    for i in range(len(odd)):
        tail = ''
        while len(tail) < ratio // 2:
            tail += even[indx]
            indx += 2
        x.append(tail + odd[i] + tail[::-1])
    print(' '.join(x))
else:
    ratio = len(even)//len(odd)
    max_length = 1
    for i in range(1,ratio+1,2):
        if (len(even)+len(odd)) % i == 0 and max_length < i:
            max_length = i
    parts = (len(even) + len(odd))//max_length
    print(parts)
    x = []
    indx = 0
    for i in range(len(odd)):
        tail = ''
        while len(tail) < max_length // 2:
            tail += even[indx]
            indx += 2
        x.append(tail + odd[i] + tail[::-1])
    middle = []
    for i in range(parts - len(odd)):
        middle.append(even.pop())
    for i in range(len(middle)):
        tail = ''
        while len(tail) < max_length // 2:
            tail += even[indx]
            indx += 2
        x.append(tail + middle[i] + tail[::-1])
    print(' '.join(x))


n = int(input())
s = list(input())
d = {}
for char in s:
    if char not in d.keys():
        d[char] = 1
    else:
        d[char] += 1

odd = []
even = []
for char in d.keys():
    for i in range(d[char] // 2):
        even.append(char)
        even.append(char)
    for i in range(d[char] % 2):
        odd.append(char)

if len(odd) <= 1:
    x = ''.join([even[i] for i in range(1, len(even), 2)])
    y = ''.join(odd)
    print(1)
    print(x + y + x[::-1])

else:
    ratio = len(even)//len(odd)
    max_length = 1
    for i in range(1,ratio+2,2):
        if n % i == 0 and max_length < i:
            max_length = i
    parts = n//max_length
    print(parts)
    x = []
    indx = 0
    for i in range(len(odd)):
        tail = ''
        while len(tail) < max_length // 2:
            tail += even[indx]
            indx += 2
        x.append(tail + odd[i] + tail[::-1])
    middle = []
    for i in range(parts - len(odd)):
        middle.append(even.pop())
    for i in range(len(middle)):
        tail = ''
        while len(tail) < max_length // 2:
            tail += even[indx]
            indx += 2
        x.append(tail + middle[i] + tail[::-1])
    print(' '.join(x))

mp,a,p={},[],[]
n=int(input())
for i in input():
    if i in mp:mp[i]+=1
    else:mp[i]=1
odd=0
for i in mp:
    if mp[i]&1:
        a.append(i)
        mp[i]-=1
        odd+=1
    if mp[i]:
        p.append(i)
m=max(1,odd)
for i in range(m,n+1):
    if not n%i:
        d=n//i
        if odd and not d&1:continue
        print(i)
        for K in range(i-m):
            a.append(p[-1])
            if mp[p[-1]]>1:mp[p[-1]]-=1
            else:p.pop()
        for k in range(i):
            s=''
            for j in range(d//2):
                s+=p[-1]
                mp[p[-1]]-=2
                if not mp[p[-1]]:p.pop()
            if odd:print(s+a.pop()+s[::-1],end=' ')
            else:print(s+s[::-1],end=' ')
        return

n=int(input())
s=list(input())
lets={}
for i in s:
    try:
        lets[i]+=1
    except:
        lets[i]=1
count=0
centre=[]
rest=[]
for i in lets.keys():
    if(lets[i]%2):
        centre.append(i)
        count+=1
    rest+=[i]*(lets[i]//2)
if(count==0):
    t=''
    for i in lets.keys():
        t=i*(lets[i]//2) + t + i*(lets[i]//2)
    print(1)
    print(t)

else:
    extra=0
    while(n%count!=0 or (n//count)%2==0):
        count+=2
        extra+=1
    for i in range(extra):
        centre+=[rest.pop()]*2
    amt=len(rest)//(count)
    temp=rest.copy()
    rest=''
    for i in temp:
        rest+=i
    print(count)
    print(rest[0:amt] + centre[0] + rest[(1)*(amt)-1::-1],end=' ')
    for i in range(1,count):
        print(rest[i*(amt):(i+1)*amt] + centre[i] + rest[(i+1)*(amt)-1:(i)*amt-1:-1],end=' ')
    print()

mp,a,p={},[],[]
n=int(input())
for i in input():
    if i in mp:mp[i]+=1
    else:mp[i]=1
odd=0
for i in mp:
    if mp[i]&1:
        a.append(i)
        mp[i]-=1
        odd+=1
    if mp[i]:
        p.append(i)
m=max(1,odd)
for i in range(m,n+1):
    if not n%i:
        d=n//i
        if odd and not d&1:continue
        print(i)
        for K in range(i-m):
            a.append(p[-1])
            if mp[p[-1]]>1:mp[p[-1]]-=1
            else:p.pop()
        for k in range(i):
            s=''
            for j in range(d//2):
                s+=p[-1]
                mp[p[-1]]-=2
                if not mp[p[-1]]:p.pop()
            if odd:print(s+a.pop()+s[::-1],end=' ')
            else:print(s+s[::-1],end=' ')
        return

import sys
import math
from collections import defaultdict,deque
def is_possible(odd,even):
	each = odd*2
	if even % each == 0:
		return True
	return False
n=int(sys.stdin.readline())
s=sys.stdin.readline()[:-1]
dic=defaultdict(int)
for i in range(n):
	dic[s[i]]+=1
odd,even = 0,0
for i in dic:
	if dic[i]%2 != 0:
		odd += 1
		even += dic[i] - 1
	else:
		even += dic[i]
if odd == 0:
	#print(0)
	ans = [0 for x in range(even)]
	cnt = 0
	for i in dic:
		while dic[i] > 0:
			ans[cnt] = i
			ans[even - cnt - 1] = i
			cnt += 1
			dic[i] -= 2
	#print(ans)
	print(1)
	print(''.join(x for x in ans))
	return
while even >= 0:
	if is_possible(odd,even):
		break
	odd += 2
	even -= 2
length = 1 + (even) // (odd)
#print(length, 'length')
ans = [deque() for _ in range(odd)]
ansb = [[] for _ in range(odd)]
ansa = [[] for _ in range(odd)]
cnt = 0
#print(dic,'dic')
for i in dic:
	if dic[i] % 2 !=0:
		ans[cnt].append(i)
		dic[i] -= 1
		cnt += 1
#print()
#print(ans,' after odd',cnt)
for i in dic:
	while dic[i] > 0:
		if cnt >= odd:
			break
		ans[cnt].append(i)
		ans[cnt + 1].append(i)
		cnt += 2
		dic[i] -= 2
	if cnt >= odd:
		break
cnt = 0
#print(ans,'ans')
for i in dic:
	#print(cnt,'cnt',i,'i')
	#print(ans[cnt])
	if dic[i] > 0:
		x = len(ans[cnt])
		while dic[i] > 0:
			ans[cnt].appendleft(i)
			ans[cnt].append(i)
			#ans[cnt] = [i] + ans[cnt] + [i]
			dic[i] -= 2
			x += 2
			if x < length:
				pass
			else:
				cnt += 1
				if cnt < odd:
					x = len(ans[cnt])
#print(ans,'ans')
#print(odd,'odd')
n = len(ans)
#print(n)
l =[]
for i in range(n):
	l.append(''.join(x for x in ans[i]))
print(n)
print(*l)