Дана непустая строка s и число k. Со строкой один раз проделывают следующую операцию:
- Разбивают строку на не более чем k непустых подстрок, то есть представляют строку s в виде конкатенации (сцепления) набора строк s = t1 + t2 + ... + tm, 1 ≤ m ≤ k.
- Некоторые из строк ti заменяются строками tir, то есть их записью справа налево.
- Строки конкатенируются обратно в том же порядке, получается строка s' = t'1t'2... t'm, где t'i равно ti или tir.
Вам требуется определить лексикографически минимальную строку, которая может получиться в результате одного применения к строке s данной операции.
Выходные данные
В единственной строке выведите лексикографически минимальную строку s', которая может получиться в результате выполнения описанной операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aba
2
|
aab
|
|
2
|
aaaabacaba
2
|
aaaaabacab
|
|
3
|
bababa
1
|
ababab
|
|
4
|
abacabadabacaba
4
|
aababacabacabad
|