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.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static MyScanner in;
    static PrintWriter out;

    /*
    20
11111111111111111123
     */

    public static void main(String[] args) throws IOException {
        in = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out), false);

        int n = in.nextInt();
        String s = in.next();

        int[] chet = new int[1000];
        int[] nechet = new int[1000];

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);

            nechet[ch]++;
            if (nechet[ch] == 2) {
                nechet[ch] = 0;
                chet[ch]++;
            }
        }

        int chetCnt = 0;
        for (int c : chet)
            chetCnt += c;
        int nechetCnt = 0;
        for (int c : nechet)
            nechetCnt += c;

        int k = bestK(chetCnt, nechetCnt, n);
        int mig = 0;
        int nechet2 = nechetCnt;
        for (int chet2 = chetCnt - 1; chet2 > 0; chet2--) {
            nechet2 += 2;
            if (nechet2 > chet2)
                break;

            int canK = bestK(chet2, nechet2, n);
            if (canK < k) {
                mig += chetCnt - chet2;
                nechetCnt = nechet2;
                chetCnt = chet2;
                k = canK;
            }
        }
//        System.out.println(mig);
        migrate(chet, nechet, mig);


        out.println(k);

        //create
        LinkedList<Character>[] ans = new LinkedList[k];
        for (int i = 0; i < k; i++)
            ans[i] = new LinkedList<>();

        if (k == 1) {
            fillNechet(ans, nechet);
            fillChet(ans, chet);
        } else if (k == n) {
            int i = 0;
            for (char ch : s.toCharArray())
                ans[i++].addLast(ch);
        } else {
            fillNechet(ans, nechet);
            fillChet(ans, chet);
        }

        //print
        for (LinkedList<Character> list : ans) {
            for (char ch : list)
                out.print(ch);
            out.print(" ");
        }
        out.println();
        out.flush();
        out.close();
    }

    static void migrate(int[] chet, int[] nechet, int m) {

        for (int i = 0; m != 0 && i < chet.length; i++) {
            if (chet[i] != 0) {
                chet[i]--;
                nechet[i] += 2;
                m--;
                i--;
            }
        }

    }

    static int bestK(int chet, int nechet, int len) {
        if (nechet == 0)
            return 1;
        else if (chet % nechet == 0)
            return nechet;
        else
            return len;
    }

    static void fillNechet(LinkedList<Character>[] arr, int[] nechet) {
        int index = -1;

        for (int i = 0; i < nechet.length; i++) {
            if (nechet[i] == 0)
                continue;

            index++;
            if (index == arr.length)
                index = 0;

            char ch = (char) i;
            arr[index].addFirst(ch);
            nechet[i]--;
            i--;
        }
    }

    static void fillChet(LinkedList<Character>[] arr, int[] chet) {
        int index = -1;

        for (int i = 0; i < chet.length; i++) {
            if (chet[i] == 0)
                continue;

            index++;
            if (index == arr.length)
                index = 0;

            char ch = (char) i;
            arr[index].addFirst(ch);
            arr[index].addLast(ch);
            chet[i]--;
            i--;
        }
    }
}

class MyScanner implements Closeable {

    public static final String CP1251 = "cp1251";

    private final BufferedReader br;
    private StringTokenizer st;
    private String last;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public MyScanner(String path) throws IOException {
        br = new BufferedReader(new FileReader(path));
    }

    public MyScanner(String path, String decoder) throws IOException {
        br = new BufferedReader(new InputStreamReader(new FileInputStream(path), decoder));
    }

    public void close() throws IOException {
        br.close();
    }

    public String next() throws IOException {
        while (st == null || !st.hasMoreElements())
            st = new StringTokenizer(br.readLine());
        last = null;
        return st.nextToken();
    }

    public String next(String delim) throws IOException {
        while (st == null || !st.hasMoreElements())
            st = new StringTokenizer(br.readLine());
        last = null;
        return st.nextToken(delim);
    }

    public String nextLine() throws IOException {
        st = null;
        return (last == null) ? br.readLine() : last;
    }

    public boolean hasNext() {
        if (st != null && st.hasMoreElements())
            return true;

        try {
            while (st == null || !st.hasMoreElements()) {
                last = br.readLine();
                st = new StringTokenizer(last);
            }
        } catch (Exception e) {
            return false;
        }

        return true;
    }

    public String[] nextStrings(int n) throws IOException {
        String[] arr = new String[n];
        for (int i = 0; i < n; i++)
            arr[i] = next();
        return arr;
    }

    public String[] nextLines(int n) throws IOException {
        String[] arr = new String[n];
        for (int i = 0; i < n; i++)
            arr[i] = nextLine();
        return arr;
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public int[] nextInts(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = nextInt();
        return arr;
    }

    public Integer[] nextIntegers(int n) throws IOException {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++)
            arr[i] = nextInt();
        return arr;
    }

    public int[][] next2Ints(int n, int m) throws IOException {
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                arr[i][j] = nextInt();
        return arr;
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public long[] nextLongs(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
            arr[i] = nextLong();
        return arr;
    }

    public long[][] next2Longs(int n, int m) throws IOException {
        long[][] arr = new long[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                arr[i][j] = nextLong();
        return arr;
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next().replace(',', '.'));
    }

    public double[] nextDoubles(int size) throws IOException {
        double[] arr = new double[size];
        for (int i = 0; i < size; i++)
            arr[i] = nextDouble();
        return arr;
    }

    public double[][] next2Doubles(int n, int m) throws IOException {
        double[][] arr = new double[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                arr[i][j] = nextDouble();
        return arr;
    }

    public boolean nextBool() throws IOException {
        String s = next();
        if (s.equalsIgnoreCase("true") || s.equals("1"))
            return true;

        if (s.equalsIgnoreCase("false") || s.equals("0"))
            return false;

        throw new IOException("Boolean expected, String found!");
    }
}