Задана строка, состоящая из строчных латинских букв.
Пара соседних букв в строке считается противной, если данные буквы так же соседние в алфавите. Например, строка «abaca» содержит противные пары на позициях \((1, 2)\) — «'ab» и \((2, 3)\) — «ba». Буквы 'a' и 'z' не считаются соседними в алфавите.
Можете ли вы так переставить местами буквы в данном строке, чтобы в ней не было противных пар? Выбирая новый порядок, помните, что нельзя добавлять в строку новые буквы или удалять уже имеющиеся. Также можно сохранить начальный порядок.
Если существует несколько ответов, выведите любой из них.
Также требуется ответить на \(T\) независимых запросов.
Выходные данные
Выведите \(T\) строк. В \(i\)-й строке должен быть записан ответ на \(i\)-й запрос.
Если ответ на \(i\)-й запрос существует, то выведите строку с новым порядком букв такую, что она не содержит противных пар. Выбирая новый порядок, помните, что нельзя добавлять в строку новые буквы или удалять уже имеющиеся. Также можно сохранить начальный порядок.
Если существует несколько ответов, выведите любой из них.
Если ответа на запрос нет, выведите «No answer».
Примечание
В первом примере ответ «bdac» также корректен.
Второй пример показывает, что только соседние буквы в алфавите неприемлемы. Одинаковые подходят.
В третьем примере множество правильных ответов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
abcd
gg
codeforces
abaca
|
cadb
gg
codfoerces
No answer
|