Вам дана строка \(s\) длиной \(n\), состоящая только из строчных латинских букв.
Вы должны сделать ровно одну операцию следующего вида:
- Выбрать любые два индекса \(i\) и \(j\) (\(1 \le i, j \le n\)). Вы можете выбрать \(i = j\).
- Установить \(s_i := s_j\).
Вам нужно минимизировать количество различных перестановок\(^\dagger\) строки \(s\). Выведите любую строку с наименьшим количеством различных перестановок после выполнения ровно одной операции.
\(^\dagger\) Перестановка строки — это расположение её символов в любом порядке. Например, «bac» является перестановкой «abc», но «bcc» — нет.
Выходные данные
Для каждого набора входных данных выведите требуемую строку \(s\) после выполнения ровно одной операции. Если есть несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных мы можем получить следующие строки за одну операцию: «abc», «bbc», «cbc», «aac», «acc», «aba» и «abb».
Строка «abc» имеет \(6\) различных перестановок: «abc», «acb», «bac», «bca», «cab», и «cba».
Строка «cbc» имеет \(3\) различных перестановки: «bcc», «cbc», и «ccb», что является наименьшим из всех получаемых строк. На самом деле, все получаемые строки, кроме «abc», имеют \(3\) перестановки, так что любая из них будет принята.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
abc
4
xyyx
8
alphabet
1
k
10
aabbccddee
6
ttbddq
|
cbc
yyyx
alphaaet
k
eabbccddee
tttddq
|