28747번 - Сложности с жетоном 다국어

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

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

• Удалить первую букву текущей строки
• Удалить вторую букву текущей строки
• Удалить предпоследнюю букву текущей строки
• Удалить последнюю букву текущей строки

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

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

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

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

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