Найкраще привітання
Limits: 2 sec., 256 MiB
Зеник приготував сюрприз для Марічки. Він власноруч зробив чудову листівку та вирішив написати найкраще привітання. Та на цьому етапі фантазія в Зеника завершилась. Тому він знайшов привітання в Інтернеті та написав його.
Подивився потім Зеник на свій подарунок та й зрозумів, що цим він Марічку не вразить. Тому він вирішив вирізати декілька букв та на їхні місця вклеїти ці ж букви, але в іншому порядку. Та, щоб Марічка не помітила цього, Зеник може вирізати не більше \(k\) букв.
Та будь-як вклеїти букви назад Зеник не може. Чомусь він вирішив, що привітання дуже сподобається Марічці, якщо воно буде лексикографічно мінімальним серед усіх можливих привітань, які він може отримати. Допоможіть йому знайти це привітання.
Рядок \(s\) вважається лексикографічно меншим, ніж рядок \(t\), якщо існує такий індекс \(і\), що \(s_1 = t_1\), \(s_2 = t_2\), …, \(s_{i-1} = t_{i-1}\) та \(s_i < t_i\) або \(s\) є префіксом \(t\).
Input
У першому рядку задано два цілих числа \(n\) та \(k\) — кількість букв у привітанні Зеника та кількість букв, які може вибрати Зеник, відповідно.
У наступному рядку задано привітання Зеника, яке він завантажив з Інтернету. Привітання складається лише з маленьких латинських букв.
Output
У єдиному рядку виведіть лексикографічно мінімальне привітання, яке може отримати Зеник.
Constraints
\(1 \le k \le n \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
7 3 acbdaxa | aabcaxd |
Notes
У повідомленні acbdaxa
Зеник може вибрати букви з
номерами 2, 4 та 7. Вирізавши та вклеївши їх назад в іншому порядку, він
може отримати aabcaxd
. Це і буде лексикографічно найменшим
привітанням.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|