E. Разрезание строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана непустая строка 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 ≤ |s| ≤ 5 000 000), состоящая из строчных букв английского алфавита. Во второй строке содержится целое число k (1 ≤ k ≤ |s|) — максимальное количество частей в разбиении.

Выходные данные

В единственной строке выведите лексикографически минимальную строку s', которая может получиться в результате выполнения описанной операции.

Примеры
Входные данные
aba
2
Выходные данные
aab
Входные данные
aaaabacaba
2
Выходные данные
aaaaabacab
Входные данные
bababa
1
Выходные данные
ababab
Входные данные
abacabadabacaba
4
Выходные данные
aababacabacabad