Statement is not available in English language
E. Оптимальная анаграмма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$. Пусть $$$t$$$ — анаграмма$$$^{\text{∗}}$$$ строки $$$s$$$.

Определим стоимость $$$t$$$ как количество строчных латинских букв $$$a, b, \ldots, z$$$, таких, что эта буква встречается в строке $$$s$$$ (тогда она встречается и в $$$t$$$), и индекс её самого левого вхождения этой буквы в строку $$$t$$$ меньше индекса самого левого вхождения в строку $$$s$$$. Для примера расчёта стоимости анаграммы обратитесь к примечанию.

Ваша задача — по заданной строке $$$s$$$ и числу $$$k$$$ найти лексикографически минимальную$$$^{\text{†}}$$$ анаграмму со стоимостью не более $$$k$$$.

$$$^{\text{∗}}$$$Строка $$$t$$$ является анаграммой строки $$$s$$$, если $$$t$$$ можно получить из $$$s$$$ перестановкой символов. Иными словами, каждая буква входит в строку $$$s$$$ и строку $$$t$$$ одинаковое число раз.

$$$^{\text{†}}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ ($$$a$$$ идёт раньше $$$b$$$ в алфавитном порядке), если и только если выполняется одно из двух условий:

  • $$$b$$$ начинается со строки $$$a$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

В первой строке содержится одно число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина строки $$$s$$$.

Во второй строке содержится строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.

В третьей строке содержится одно число $$$k$$$ ($$$0 \le k \le 26$$$) — ограничение на стоимость анаграммы.

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

Выведите одну строку — лексикографически минимальную анаграмму строки $$$s$$$ со стоимостью не более $$$k$$$.

Система оценки

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие, когда строка $$$s$$$ состоит только из символов a и b, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \le 8$$$, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \le 1000$$$, наберут не менее $$$50$$$ баллов.

Решения, корректно работающие при $$$k=0$$$, наберут не менее $$$30$$$ баллов.

Примеры
Входные данные
6
banana
1
Выходные данные
aaabnn
Входные данные
6
banana
0
Выходные данные
baaann
Входные данные
8
bbaabbaa
0
Выходные данные
bbaaaabb
Примечание

В первом примере s="banana", а t="aaabnn". Строка $$$t$$$ является анаграммой $$$s$$$, так как её можно получить перестановкой символов. Стоимость $$$t$$$ определяется так:

  • Буква a первый раз встречается в $$$s$$$ на позиции $$$2$$$ (в $$$1$$$-нумерации), а в $$$t$$$ на позиции $$$1$$$, поэтому она увеличивает стоимость на $$$1$$$.
  • Буква b в строке $$$s$$$ находится на позиции $$$1$$$, а в $$$t$$$ — на позиции $$$4$$$. Значит, она встречается в $$$s$$$ не позже, чем в $$$t$$$, поэтому она не увеличивает стоимость.
  • Буква n в строке $$$s$$$ находится на позиции $$$3$$$, а в $$$t$$$ — на позиции $$$5$$$. Значит, она встречается в $$$s$$$ не позже, чем в $$$t$$$, поэтому она не увеличивает стоимость.
  • Остальные буквы не встречаются в строках.

Итого, стоимость такой анаграммы равна $$$1$$$.

Во втором и третьем примере анаграммы имеют стоимость $$$0$$$.