← 返回题目列表

Codeforces · 883/H

H. 回文剪切

中文机器翻译题面 查看原题

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