Сложности с жетоном

시간 제한2초메모리 제한1024 MB

요약

문자열 s에서 첫 글자, 둘째 글자, 끝에서 둘째 글자, 마지막 글자를 반복해 지울 수 있을 때 얻을 수 있는 길이 k 문자열 가운데 사전순으로 가장 작은 것을 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 그리디, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

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

출력

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

예제2

예제 1
입력
```
abacaba
3
```
예상 출력
```
aaa
```
예제 2
입력
```
qwerty
2
```
예상 출력
```
er
```