Дана строка \(s\) длины \(n\), состоящая из строчных латинских букв, а также целое число \(k\). За один шаг вы можете выполнить одну любую операцию из следующих двух:
- Выбрать индекс \(i\) (\(1 \le i \le n - 2\)), затем поменять местами \(s_{i}\) и \(s_{i+2}\).
- Выбрать индекс \(i\) (\(1 \le i \le n-k+1\)), затем развернуть порядок следования букв на отрезке \([i,i+k-1]\) строки. Формально, если строка в текущий момент равна \(s_1\ldots s_{i-1}s_is_{i+1}\ldots s_{i+k-2}s_{i+k-1}s_{i+k}\ldots s_{n-1}s_n\), то она заменяется на \(s_1\ldots s_{i-1}s_{i+k-1}s_{i+k-2}\ldots s_{i+1}s_is_{i+k}\ldots s_{n-1}s_n\).
Вы можете сделать произвольное (возможно, нулевое) число шагов. Найдите лексикографически наименьшую строку, которую можно получить после какого-либо числа шагов.
Строка \(a\) лексикографически меньше строки \(b\) такой же длины, если выполняется следующее:
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите лексикографически наименьшую строку, которую можно получить после какого-либо (возможно, нулевого) числа шагов.
Примечание
В первом наборе входных данных можно получить строку «aimn», выполняя следующие операции:
- Развернуть отрезок \([3,4]\). Строка превратится в «niam».
- Поменять местами \(s_1\) и \(s_3\). Строка превратится в «ainm».
- Развернуть отрезок \([3,4]\). Строка превратится в «aimn».
Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aimn». Значит, «aimn» и является ответом.
Во втором наборе входных данных можно получить строку «aandp», выполняя следующие операции:
- Поменять местами \(s_3\) и \(s_5\). Строка превратится в «paadn».
- Поменять местами \(s_1\) и \(s_3\). Строка превратится в «aapdn».
- Поменять местами \(s_3\) и \(s_5\). Строка превратится в «aandp».
Можно доказать, что невозможно получить строку, лексикографически меньшую, чем «aandp». Значит, «aandp» и является ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 2
nima
5 3
panda
9 2
theforces
7 3
amirfar
6 4
rounds
|
aimn
aandp
ceefhorst
aafmirr
dnorsu
|