После того, как Антон отклонил \(10^{100}\) задач на структуры данных, Errorgorn очень зол на него и решил его убить.
ДНК Антона можно представить в виде строки \(a\), которая содержит только символы из строки «ANTON» (всего \(4\) различных символов).
Errorgorn может заменить ДНК Антона на строку \(b\), которая должна быть перестановкой \(a\). Однако тело Антона может защититься от этой атаки. За \(1\) секунду его тело может поменять местами \(2\) соседних символа его ДНК, чтобы превратить ее обратно в \(a\). Тело Антона умно и будет использовать минимальное количество ходов.
Чтобы максимизировать вероятность смерти Антона, Errorgorn хочет изменить ДНК Антона на строку, которая максимизирует время, необходимое телу Антона для возвращения к его исходному ДНК. Но поскольку Errorgorn занят решением новых задач на структуры данных, ему нужна ваша помощь, чтобы найти лучшую строку \(B\). Сможете ли вы ему помочь?
Выходные данные
Для каждого набора входных данных выведите единственную строку \(b\). Если ответов несколько, вы можете вывести любой из них. \(b\) должна быть перестановкой строки \(a\).
Примечание
Для первого набора входных данных, телу Антона требуется \(7\) секунд, чтобы превратить NNOTA в ANTON:
NNOTA \(\to\) NNOAT \(\to\) NNAOT \(\to\) NANOT \(\to\) NANTO \(\to\) ANNTO \(\to\) ANTNO \(\to\) ANTON.
Обратите внимание, что нельзя вывести такие строки, как AANTON, ANTONTRYGUB, AAA и anton, так как они не являются перестановкой ANTON.
Для первого тестового случая телу Антона требуется \(2\) секунды, чтобы преобразовать AANN в NAAN. Обратите внимание, что другие строки, такие как NNAA и ANNA также будут приняты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
ANTON
NAAN
AAAAAA
OAANTTON
|
NNOTA
AANN
AAAAAA
TNNTAOOA
|