Найкраще привітання
Обмеження: 2 сек., 256 МіБ
Зеник приготував сюрприз для Марічки. Він власноруч зробив чудову листівку та вирішив написати найкраще привітання. Та на цьому етапі фантазія в Зеника завершилась. Тому він знайшов привітання в Інтернеті та написав його.
Подивився потім Зеник на свій подарунок та й зрозумів, що цим він Марічку не вразить. Тому він вирішив вирізати декілька букв та на їхні місця вклеїти ці ж букви, але в іншому порядку. Та, щоб Марічка не помітила цього, Зеник може вирізати не більше \(k\) букв.
Та будь-як вклеїти букви назад Зеник не може. Чомусь він вирішив, що привітання дуже сподобається Марічці, якщо воно буде лексикографічно мінімальним серед усіх можливих привітань, які він може отримати. Допоможіть йому знайти це привітання.
Рядок \(s\) вважається лексикографічно меншим, ніж рядок \(t\), якщо існує такий індекс \(і\), що \(s_1 = t_1\), \(s_2 = t_2\), …, \(s_{i-1} = t_{i-1}\) та \(s_i < t_i\) або \(s\) є префіксом \(t\).
Вхідні дані
У першому рядку задано два цілих числа \(n\) та \(k\) — кількість букв у привітанні Зеника та кількість букв, які може вибрати Зеник, відповідно.
У наступному рядку задано привітання Зеника, яке він завантажив з Інтернету. Привітання складається лише з маленьких латинських букв.
Вихідні дані
У єдиному рядку виведіть лексикографічно мінімальне привітання, яке може отримати Зеник.
Обмеження
\(1 \le k \le n \le 10^5\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 3 acbdaxa | aabcaxd |
Примітки
У повідомленні acbdaxa
Зеник може вибрати букви з
номерами 2, 4 та 7. Вирізавши та вклеївши їх назад в іншому порядку, він
може отримати aabcaxd
. Це і буде лексикографічно найменшим
привітанням.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|