Сложности с жетоном
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы знаете, жетоны, которые Сэм носит на шее — своего рода ключи, позволяющие подключать города к общей сети. Однако на самом же деле всё не так просто, и чтобы подключить город, требуется не только наличие ключа, но и специальный пароль.

Сам пароль неизвестен, однако когда Бриджет давала Сэму задание, она так же рассказала, что пароль можно получить из определенной строки $$$s$$$, выполнив несколько раз следующие действия:

Связываясь с голограммой Амели в течении путешествия, Сэм узнал, что пароль имеет длину $$$k$$$, а так же является лексикографически минимальным словом длины $$$k$$$ среди всех, которые можно получить из $$$s$$$ описанным образом.

Всю информацию Сэм уже собрал, так что теперь задача найти пароль за вами. Помогите Сэму и выведите минимальную строку длины $$$k$$$, которую можно получить из $$$s$$$ указанным образом.

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

В первой строке дана строка $$$s$$$, состоящая из строчных латинских букв ($$$1 \le |s| \le 500\,000$$$).

Во второй строке дано натуральное число $$$k$$$ — длина пароля ($$$1 \le k \le |s|$$$).

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

Выведите строку — искомый пароль.

Примеры

Входные данные
abacaba
3
Выходные данные
aaa
Входные данные
qwerty
2
Выходные данные
er