Sorting Trimmer
TopCoder TCO2014 Round 1A
Time Limit: 0.1s, Memory Limit: 64MiB
На Кристина за играчка
подариха ѝ резачка.
Ха сега деца кажете,
где са ѝ ръцете?

Не, сериозно. Първо, подариха резачката нa Ели, а не на Крис. Второ, резачката, която подариха на Ели, е различна. Тя е с мощност L и работи по следния начин.

Избира се подстринг с дължина L на даден стринг S (тоест L на брой последователни символа от S). Устройството сортира символите в избрания подстринг и изрязва всичко надясно от края му (потенциално нищо, ако момичето е избрало последните L букви).

Ели иска да експериментира с новата си придобивка. Тя има стринга S с дължина N, съставен от цифри и букви от латинската азбука. Сега момичето се чуди какъв е лексикографски най-малкият стринг, който може да бъде получен след нула или повече ползвания на резачката.

Един стринг S1 е лексикографски по-малък от друг стринг S2, ако S1 е префикс на S2 или S1[i] < S2[i], където i е първият индекс, където се различават. За лексикографска подредба на символите ползвайте наредбата в ASCII таблицата (цифрите са преди буквите, а главните букви са преди малките).
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и L – съответно дължината на първоначалния стринг, с който разполага Ели, и мощността на резачката. Следва ред, съдържащ стринг S с N символа от азбуката {'0'-'9', 'A'-'Z', 'a'-'z'}.
Изход
На единствен ред на стандартния изход изведете последователност от символи с дължина между L и N, включително – лексикографски най-малкият стринг, който може да бъде получен.
Ограничения
  • 1 ≤ LN ≤ 10,000,000
Примерен Вход Примерен Изход
6 3 espr1t 1ep
7 7 Bazinga Baaginz
32 13 BasiGolemiteRyki4uekTuiAzLiSumWe 4ABGLRSTWaeee
В първия пример Ели може да ползва уреда на es[pr1]t, получавайки es1pr, след което e[s1p]r -> e1ps и накрая [e1p]s -> 1ep.
Мрън!