Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.
Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.
Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна 6, так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна 3, так как только подстроки длины 1 являются палиндромами.
Вам дана строка s. Вы можете произвольным образом переставлять символы в ней. Требуется получить строку, имеющую максимальную палиндромность.
Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 100000) — длина строки s.
Во второй строке задана строка s, состоящая из n строчных букв латинского алфавита.
Выходные данные
Выведите строку t, которая состоит из тех же символов (с учётом кратностей), что и s, и имеет максимальную палиндромность среди всех строк, которые могут быть получены из s перестановкой символов.
Если подходящих строк несколько, выведите любую.
Примечание
В первом примере у строки « ololo » есть 9 подстрок-палиндромов: « o », « l », « o », « l », « o », « olo », « lol », « olo », « ololo ». Обратите внимание, что некоторые подстроки совпадают, но учитываются несколько раз.
Во втором примере палиндромность строки « abccbaghghghgdfd » равна 29.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
oolol |
ololo |
| 2 |
16
gagadbcgghhchbdf |
abccbaghghghgdfd |