如果从左到右和从右到左读取相同的非空字符串,则称为回文字符串。例如,“abcba”、“a”和“abba”是回文,而“abab”和“xy”则不是。
如果一个字符串可以通过从该字符串的开头和结尾删除一些(可能为零)个字符来获得,则该字符串称为另一个字符串的子字符串。例如,“abc”、“ab”和“c”是字符串“abc”的子字符串,而“ac”和“d”则不是。
让我们将字符串的回文计数定义为其回文子字符串的数量。例如,字符串“aaa”的回文数为$$$6$$$,因为它的所有子串都是回文;字符串“abc”的回文数为$$$3$$$,因为只有长度为$$$1$$$的子串是回文。
给你一个字符串$$$s$$$。您可以任意重新排列其字符。您的目标是获得回文计数最大可能值的字符串。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 字符串 $$$s$$$ 的长度。
第二行包含字符串 $$$s$$$,该字符串恰好由 $$$n$$$ 拉丁字母小写字符组成。
输出
打印字符串 $$$t$$$,它由与字符串 $$$s$$$ 相同的字符集组成(并且每个字符出现的次数完全相同)。此外,$$$t$$$ 应该具有所有此类字符串中回文计数的最大可能值。
如果有多个这样的字符串,则打印其中任何一个。
示例
输入 #1
5 oolol
输出 #1
ololo
输入 #2
16 gagadbcgghhchbdf
输出 #2
abccbaghghghgdfd
注意
在第一个示例中,字符串“ololo”具有 $$$9$$$ 回文子字符串:“o”、“l”、“o”、“l”、“o”、“olo”、“lol”、“olo”、“ololo”。请注意,即使某些子字符串重合,它们也会按照它们在结果字符串中出现的次数进行计数。
在第二个示例中,字符串“abccbaghghghgdfd”的回文计数为 $$$29$$$。