Поздравляю, вы поступили в Центр Помощи Магистрам! Однако, на уроках вам было безумно скучно и вам надоело ничего не делать, поэтому вы придумали себе развлечение.
Вам дана строка \(s\) и чётное число \(n\). Есть два типа операций, которые вы можете к ней применять:
- Добавить в конец строки \(s\) перевёрнутую строку \(s\) (например, если \(s = \) cpm, то после применения операции \(s = \) cpmmpc).
- Перевернуть текущую строку \(s\) (например, если \(s = \) cpm, то после применения операции \(s = \) mpc).
Требуется определить лексикографически минимальную\(^{\dagger}\) строку, которую можно получить после применения ровно \(n\) операций. Обратите внимание, что вы можете применять операции разных типов в произвольном порядке, но суммарно вы должны применить ровно \(n\) операций.
\(^{\dagger}\)Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) является префиксом \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите одну строку — лексикографически минимальную строку, которую можно получить после применения ровно \(n\) операций.
Примечание
В первом наборе входных данных можно применить операцию второго типа (то есть перевернуть строку \(s\)) \(4\) раза. Тогда строка \(s\) останется равной cpm.
Во втором наборе входных данных можно сделать следующее:
- Применить операцию второго типа, после чего \(s\) станет равной birg.
- Применить операцию первого типа (то есть добавить в конец строки \(s\) перевёрнутую строку \(s\)), после чего \(s\) станет равной birggrib.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba
|
cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba
|