Let's call a palindrome a non-empty string that reads the same from right to left and from left to right. For example, " abcba "," a " and « abba » are palindromes, and " abab » and « xy » are not.
Let's call a substring of a string a string obtained by discarding some (possibly zero) number of characters from the beginning and from the end of the string. For example, " abc "," ab » and « c » are substrings of the string « abc ", and « ac » and « d » are not.
Let's call the palindromicity of a string the number of its substrings that are palindromes. For example, the palindromic string « aaa " is 6, since all its substrings are palindromes, and the palindromicity of the string « abc " is 3 because only substrings of length 1 are palindromes.
You are given a string s. You can arbitrarily rearrange the characters in it. It is required to get a string that has the maximum palindromicity.
Input
The first line contains an integer n (1 ≤ n ≤ 100000) — string length s.
The second line contains a string s, consisting of n lowercase Latin letters.
Imprint
Output a string t that consists of the same characters (including multiplicities) as s and has the maximum palindromicity among all strings that can be obtained from s by permuting characters.
If there are several matching lines, print any one.
Note
In the first example, the string « ololo " there are 9 palindrome substrings: « o "," l "," o "," l "," o "," olo "," lol "," olo "," ololo ". Note that some substrings match but are counted multiple times.
In the second example, the palindromicity of the string « abccbaghghghgdfd » is 29.
Examples
| # |
Input |
Output |
| 1 |
5
oolol |
ololo |
| 2 |
16
gagadbcgghhchbdf |
abccbaghghghgdfd |