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