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

문제

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

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

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

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

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

입력

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

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

출력

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

제한

힌트