{"raw_statement":[{"iden":"statement","content":"Kolya has a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits.\n\nHe 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_.\n\nYour 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."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 4·105) — the length of string _s_.\n\nThe second line contains a string _s_ of length _n_ consisting of lowercase and uppercase Latin letters and digits."},{"iden":"output","content":"Print to the first line an integer _k_ — minimum number of palindromes into which you can cut a given string.\n\nPrint 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."},{"iden":"examples","content":"Input\n\n6\naabaac\n\nOutput\n\n2\naba aca \n\nInput\n\n8\n0rTrT022\n\nOutput\n\n1\n02TrrT20 \n\nInput\n\n2\naA\n\nOutput\n\n2\na A"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Kolya 有一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\\n\\n他希望重新排列 $s$ 中的字符，并将其切割成最少数量的子串，使得每个子串都是回文，且所有子串的长度 _相同_。回文是指正读和反读都相同的字符串，例如 _madam_ 或 _racecar_。\\n\\n你的任务是帮助 Kolya，确定在允许重新排列 $s$ 中的字母后，最少能将该字符串切割成多少个长度相等的回文串。\\n\\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 4·10^5$) —— 字符串 $s$ 的长度。\\n\\n第二行包含一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\\n\\n请在第一行输出一个整数 $k$ —— 你能将给定字符串切割成的最少回文串数量。\\n\\n请在第二行输出 $k$ 个字符串 —— 这些回文串本身。用空格分隔。你可以按任意顺序输出回文串，但它们都必须具有相同的长度。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $n$ ($1 ≤ n ≤ 4·10^5$) —— 字符串 $s$ 的长度。第二行包含一个长度为 $n$ 的字符串 $s$，由小写和大写拉丁字母及数字组成。\"},{\"iden\":\"output\",\"content\":\"请在第一行输出一个整数 $k$ —— 你能将给定字符串切割成的最少回文串数量。请在第二行输出 $k$ 个字符串 —— 这些回文串本身。用空格分隔。你可以按任意顺序输出回文串，但它们都必须具有相同的长度。\"},{\"iden\":\"examples\",\"content\":\"输入6aabaac输出2aba aca 输入80rTrT022输出102TrrT20 输入2aA输出2a A \"}]\n\n请注意：原始输入中 \"Input80rTrT022\" 和 \"Output102TrrT20\" 等部分存在格式问题（缺少换行），但在题面中应视为独立的测试用例。翻译已忠实保留原始格式，仅翻译自然语言部分，数学公式和下划线强调均未改动。","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string $ s $.  \nLet $ \\mathcal{C} $ be the multiset of character frequencies in $ s $, i.e., $ \\mathcal{C} = \\{ (c, f_c) \\mid c \\in \\text{alphabet}, f_c = \\text{count of } c \\text{ in } s \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 4 \\cdot 10^5 $  \n2. Each character in $ s $ is a lowercase/uppercase Latin letter or digit.  \n\n**Objective**  \nFind the minimum integer $ k \\geq 1 $ such that $ s $ can be rearranged and partitioned into $ k $ palindromic substrings of equal length $ \\ell = n/k $, where:  \n- Each palindrome has length $ \\ell $,  \n- $ k \\mid n $,  \n- The multiset $ \\mathcal{C} $ admits a decomposition into $ k $ palindromes of length $ \\ell $.  \n\nA string of length $ \\ell $ is a palindrome if at most one character has an odd frequency within it.  \nThus, for the entire multiset $ \\mathcal{C} $, the total number of characters with odd frequency, denoted $ o $, must satisfy $ o \\leq k $, since each palindrome can accommodate at most one odd-frequency character.  \n\n**Minimization Goal**  \nMinimize $ k $ such that:  \n- $ k \\mid n $,  \n- $ k \\geq o $,  \n- $ \\ell = n/k $ is an integer.  \n\n**Output**  \n- First line: $ k $  \n- Second line: $ k $ palindromes of length $ \\ell = n/k $, formed by rearranging $ s $, each being a palindrome.","simple_statement":null,"has_page_source":false}