C. Телефонные номера
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

И где здесь телефонные номера?

Дана строка s из строчных букв английского алфавита и число k. Найдите лексикографически минимальную строку t, имеющую длину k, множество букв которой является подмножеством множества букв s и s лексикографически меньше t.

Гарантируется, что ответ существует.

Обратите внимание, что под множеством букв строки подразумевается множество, а не мультимножество. В частности, множество букв строки abadaba это {a, b, d}.

Строка p считается лексикографически меньше строки q, если p — префикс q, не равный q или существует i такое, что pi < qi и для всех j < i выполнено pj = qj. Например, abc лексикографически меньше abcd , abd лексикографически меньше abec, afa лексикографически не меньше ab и a лексикографически не меньше a.

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

В первой строке через пробел заданы два целых числа n и k (1 ≤ n, k ≤ 100 000) — длина строки s и необходимая длина строки t.

Во второй строке задана строка s, состоящая из n строчных букв английского алфавита.

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

Выведите строку t, удовлетворяющую условиям, описанным выше.

Гарантируется, что ответ существует.

Примеры
Входные данные
3 3
abc
Выходные данные
aca
Входные данные
3 2
abc
Выходные данные
ac
Входные данные
3 3
ayy
Выходные данные
yaa
Входные данные
2 3
ba
Выходные данные
baa
Примечание

В первом примере список строк t длины 3, подходящих под условие, что множество букв t — подмножество множества букв s, таков: aaa, aab, aac, aba, abb, abc, aca, acb, .... Из них лексикографически больше abc: aca, acb, .... Лексикографически минимальная из них — aca.