Как вы знаете, жетоны, которые Сэм носит на шее — своего рода ключи, позволяющие подключать города к общей сети. Однако на самом же деле всё не так просто, и чтобы подключить город, требуется не только наличие ключа, но и специальный пароль.
Сам пароль неизвестен, однако когда Бриджет давала Сэму задание, она так же рассказала, что пароль можно получить из определенной строки $$$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