Problem: 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·105) — 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 

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
		Thread th = new Thread(null, new Runnable(){public void run(){new Task1().solve(in, out);}},"Task1",1<<24);
		try{
			th.start();
			th.join();
		} catch(InterruptedException e){}
		out.close();
	}

	static class Task1{
		static final int MOD = 1000000007;
		static final int MAX = 400001;
		static final int R = 256;

		public void solve(InputReader in, PrintWriter out){
			int n = in.nextInt();
			ArrayList<Integer> divisors = new ArrayList<Integer>();
			for(int i=1; i*i<=n; i++){
				if(n%i==0){
					if(i%2==1 || (n/i)%2==1){
						divisors.add(i);
						if(i!=n/i) divisors.add(n/i);
					}
				}
			}
			Collections.sort(divisors);
			/*for(Integer i: divisors)
				out.println(i);*/

			//if(1>0) return;
			String s = in.next();
			int[] hash = new int[R];
			for(int i=0; i<s.length(); i++) hash[s.charAt(i)]++;

			int start = 0, even = 0, odd = 0, ec = 0, oc = 0;
			ArrayList<Character> E = new ArrayList<Character>(), O = new ArrayList<Character>();
			for(int i=0; i<R; i++){
				int temp = hash[i];
				while(temp>0){
					if(temp==1){
						O.add((char)i);
						temp = 0;
					} else {
						E.add((char)i);
						temp -= 2;
					}
				}
				even += hash[i]/2;
				odd += hash[i]%2;
			}

			/*out.println("---------------------");
			for(Character c: E)
				out.print(c+"");
			out.println();
			for(Character c: O)
				out.print(c+"");
			out.println();
			out.println(odd+" "+even);
			out.println("--------------------");*/
			if(n%2==0 && odd==0){
				out.println(1);
				StringBuilder s1 = new StringBuilder("");
				StringBuilder s3 = new StringBuilder("");
				for(int j=0; j<even; j++){
					s1.append(E.get(ec));
					s3.append(E.get(ec++));
				}
				s3.reverse();
				out.print(s1.toString()+s3.toString()+" ");
				return;
			} else if(n%2==1 && odd==1){
				out.println(1);
				StringBuilder s1 = new StringBuilder("");
				StringBuilder s3 = new StringBuilder("");
				for(int j=0; j<even; j++){
					s1.append(E.get(ec));
					s3.append(E.get(ec++));
				}
				s3.reverse();
				out.print(s1.toString()+O.get(oc++)+s3.toString()+" ");
				return;
			}

			boolean flag = false;
			while(start<divisors.size()){
				int first = divisors.get(start);	// number
				int second = n/first;				// length
				if(odd == first){
					// this is the answer
					flag = true;
					out.println(first);
					for(int i=0; i<first; i++){
						StringBuilder s1 = new StringBuilder("");
						StringBuilder s2 = new StringBuilder("");
						StringBuilder s3 = new StringBuilder("");
						s2.append(O.get(oc++));
						for(int j=0; j<second/2; j++){
							s1.append(E.get(ec));
							s3.append(E.get(ec++));
						}
						s3.reverse();
						out.print(s1.toString()+s2.toString()+s3.toString()+" ");
					}
					break;
				} else if(odd<first && (first-odd)/2<=even && (first-odd)%2==0){
					// break some even into odds
					even -= (first-odd)/2;
					for(int j=0; j<(first-odd)/2; j++){
						O.add(E.get(ec));
						O.add(E.get(ec++));
					}
					flag = true;
					out.println(first);
					for(int i=0; i<first; i++){
						StringBuilder s1 = new StringBuilder("");
						StringBuilder s2 = new StringBuilder("");
						StringBuilder s3 = new StringBuilder("");
						s2.append(O.get(oc++));
						for(int j=0; j<second/2; j++){
							s1.append(E.get(ec));
							s3.append(E.get(ec++));
						}
						s3.reverse();
						out.print(s1.toString()+s2.toString()+s3.toString()+" ");
					}
					break;
				}else {
					start++;
				}
			}

			if(!flag){
				out.println(n);
				for(int i=0; i<n; i++){
					out.print(s.charAt(i)+" ");
				}
			}
		}

		long gcd(long a, long b){
			while(a>0){
				long rem = b%a;
				b = a;
				a = rem;
			}
			return b;
		}
		long expo(long a, long b, long MOD){
			long result = 1;
			while (b>0){
				if (b%2==1) result=(result*a)%MOD;
				b>>=1;
				a=(a*a)%MOD;
			}
			return result%MOD;
		}
		long inverseModullo(long numerator, long denominator, long MOD){
			return ((numerator )*(expo(denominator, MOD-2, MOD))) ;
		}
	}

	static class Task2{
		public void solve(InputReader in, PrintWriter out){
			//
		}
	}
 	static class DijkstraSP {
		long[] distTo;
		DirectedEdge[] edgeTo;
		IndexMinPQ<Long> pq;
		
		public DijkstraSP(EdgeWeightedDigraph G, int s){
			distTo= new long[G.V()];
			edgeTo= new DirectedEdge[G.V()];
			pq= new IndexMinPQ<Long>(G.V());			//maxN = G.V()
			
			for(int i=0; i<G.V(); i++){
				distTo[i]=Long.MAX_VALUE;
			}
			distTo[s]=0;
			
			pq.insert(s, 0L);
			while(!pq.isEmpty()){
				int v = pq.delMin();
				for(DirectedEdge e: G.adj(v)){
					relax(e);
				}
			}
		}
		
		private void relax(DirectedEdge e){
			int v=e.from(), w=e.to();
			if(distTo[w] > distTo[v]+e.weight()){
				distTo[w]= distTo[v]+e.weight();
				edgeTo[w]= e;
				
				if(pq.contains(w)){
					if(pq.keyOf(w)>distTo[w]) pq.changeKey(w, distTo[w]);
				}
				else pq.insert(w, distTo[w]);
			}
		}
	}
	static class EdgeWeightedDigraph {
		private final int V;
		private LinkedList<DirectedEdge>[] adj;
		@SuppressWarnings("unchecked")
		public EdgeWeightedDigraph(int V){
			this.V=V;
			adj=(LinkedList<DirectedEdge>[])new LinkedList[V];
			for(int i=0; i<V; i++){
				adj[i]=new LinkedList<DirectedEdge>();
			}
		}
		public void addEdge(DirectedEdge e){
			adj[e.from()].add(e);
		}
		public Iterable<DirectedEdge> adj(int v){
			return adj[v];
		}
		public int V(){
			return V;	//number of vertices
		}
	}
	static class DirectedEdge {
		private int v, w;
		private long weight;
		public DirectedEdge(int v, int w, long weight){
			this.v=v;
			this.w=w;
			this.weight=weight;
		}
		public int from(){
			return v;
		}
		public int to(){
			return w;
		}
		public long weight(){
			return weight;
		}
	}
	static class IndexMinPQ<Key extends Comparable<Key>>{
		private int[] a, b;
		private Key[] keys;
		private int N, maxN;
		
		@SuppressWarnings("unchecked")
		public IndexMinPQ(int capacity){
			this.maxN=capacity-1; this.N=0;
			this.a=new int[maxN+1];	this.b=new int[maxN+1];
			this.keys=(Key[])new Comparable[maxN+1];
			for(int i=0; i<maxN+1; i++) a[i]=-1;	
		}
		
		public boolean isEmpty(){ return N==0; }

		public int size(){ return N; }

		public boolean contains(int index){ return a[index] != -1; }

		public void insert(int index, Key key){
			N++;
			a[index]=N-1; b[N-1]=index;
			keys[index]=key;
			swim(N-1);
		}

		public int minIndex(){ return b[0]; }

		public Key minKey(){ return keys[b[0]]; }

		public Key keyOf(int index){ return keys[index]; }

		public int delMin(){
			int min=b[0];
			exch(0,--N);
			sink(0);
			a[min]= -1;
			b[N]= -1;
			return min;
		}

		public void changeKey(int index, Key newKey){
			if(contains(index)){
				keys[index]=newKey;
				swim(a[index]);
				sink(a[index]);
			}
			else throw new IllegalArgumentException("There is no key associated with this index.");
		}

		/* General Helper Functions */
		private boolean greater(int i, int j){
			return keys[b[i]].compareTo( keys[b[j]] ) > 0;
		}

		private void exch(int i, int j){
			int swap=b[i];
			b[i]=b[j];	b[j]=swap;
			a[b[i]]=i;	a[b[j]]=j;
		}

		/* Heap Helper Functions */
		private void swim(int child){
			int root=(child-1)/2;
			while(greater(root, child)){
				exch(root, child);
				child=root;
				root=(child-1)/2;
			}
		}

		private void sink(int root){
			int child=2*root +1;
			while(child<N){
				if(child<N-1)
					if(greater(child, child+1)) child++;
				if(greater(root, child))
					exch(root, child);
				else break;

				root=child;
				child=2*root+1;
			}
		}
	}

	static class InputReader{
		final InputStream stream;
		final byte[] buf = new byte[8192];
		int curChar, numChars;
		SpaceCharFilter filter;
		public InputReader(){
			this.stream = System.in;
		}
		public int read(){
			if(numChars == -1) throw new InputMismatchException();
			if(curChar >= numChars){
				curChar = 0;
				try{
					numChars = stream.read(buf);
				} catch(IOException e){
					throw new InputMismatchException();
				}
				if(numChars <= 0) return -1;
			}
			return buf[curChar++];
		}
		public int nextInt(){
			int c = read();
			while(isSpaceChar(c)) c = read();
			int sgn = 1;
			if(c == '-'){
				sgn = -1;
				c = read();
			}
			int res = 0;
			do{
				if(c<'0' || c>'9') throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while(!isSpaceChar(c));
			return res*sgn;
		}
		public long nextLong(){
			int c = read();
			while(isSpaceChar(c)) c = read();
			int sgn = 1;
			if(c == '-'){
				sgn = -1;
				c = read();
			}
			long res = 0;
			do{
				if(c<'0' || c>'9') throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while(!isSpaceChar(c));
			return res*sgn;
		}
		public String next(){
			int c = read();
			while(isSpaceChar(c)) c = read();
			StringBuilder res = new StringBuilder();
			do{
				res.appendCodePoint(c);
				c = read();
			}while(!isSpaceChar(c));
			return res.toString();
		}
		public boolean isSpaceChar(int c){
			if(filter != null) return filter.isSpaceChar(c);
			return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
		}
		public interface SpaceCharFilter{
			public boolean isSpaceChar(int ch);
		}
	}
}