Kolya 有一个长度为 n 的字符串 s,由小写和大写拉丁字母和数字组成。
他想重新排列s中的符号,并将其切割成最少数量的部分,使得每个部分都是回文,并且所有部分的长度相同。回文是向后读与向前读相同的字符串,例如 madam 或 Racecar。
你的任务是帮助 Kolya 并确定将 s 切成等长回文的最小数量,前提是允许在切割之前重新排列 s 中的字母。
输入
第一行包含一个整数 n (1 ≤ n ≤ 4·105) — 字符串 s 的长度。
第二行包含长度为 n 的字符串 s,由小写和大写拉丁字母和数字组成。
输出
在第一行打印一个整数 k — 可以将给定字符串切割成的最小回文数。
打印到第二行 k 个字符串——回文本身。用空格将它们分开。您可以按任意顺序打印回文。它们都应该具有相同的长度。
示例
输入 #1
6 aabaac
输出 #1
2 aba aca
输入 #2
8 0rTrT022
输出 #2
1 02TrrT20
输入 #3
2 aA
输出 #3
2 a A