Черепаха дает вам строку \(s\), состоящую из строчных латинских букв.
Черепаха считает пару целых чисел \((i, j)\) (\(1 \le i < j \le n\)) приятной парой, если и только если существует целое число \(k\), такое что \(i \le k < j\) и выполняются оба из следующих двух условий:
- \(s_k \ne s_{k + 1}\);
- \(s_k \ne s_i\) или \(s_{k + 1} \ne s_j\).
Кроме того, Черепаха считает пару целых чисел \((i, j)\) (\(1 \le i < j \le n\)) хорошей парой, если и только если \(s_i = s_j\) или \((i, j)\) является приятной парой.
Черепаха хочет переставить буквы в строке \(s\) так, чтобы количество хороших пар было максимизировано. Пожалуйста, помогите ей!
Выходные данные
Для каждого набора выведите строку \(s\) после перестановки букв, которая максимизирует количество хороших пар. Если есть несколько ответов, выведите любой из них.
Примечание
В первом наборе \((1, 3)\) является хорошей парой в строке из переставленных букв. Можно заметить, что мы не можем переставить буквы так, чтобы количество хороших пар было больше \(1\). bac и cab также могут быть ответом.
Во втором наборе \((1, 2)\), \((1, 4)\), \((1, 5)\), \((2, 4)\), \((2, 5)\), \((3, 5)\) являются хорошими парами в строке из переставленных букв. efddd также может быть ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces
|
acb
ddedf
urtlet
pppppppp
codeforces
|