Substring Sorter
TopCoder SRM 606
Time Limit: 0.2s, Memory Limit: 64MiB
Ели има стринг S с дължина N и магическо устройство със сила L. Устройството прави следното: подавайки му индекс i (0 ≤ i ≤ N - L), то сортира подстринга с дължина L, започващ в индекс i. По-точно, устройството пренарежда в азбучен ред символите S[i], S[i + 1], ..., S[i + L - 1], включително.
Нека, например, S е "TOPCODER" и силата на устройството L е 5. Ако момичето ползва устройството в индекс 0, тя ще получи "COOPTDER" тъй като ще сортира "TOPCO" в "COOPT". Ако, обаче, го използва в индекс 2, тя ще сортира "PCODE" в "CDEOP" и ще получи "TOCDEOPR".
За съжаление, нейното устройство има дефект, поради който може да бъде използвано максимум веднъж. Сега момичето се чуди кой е лексикографски най-малкият стринг, който може да получи от S ползвайки го максимум веднъж?
Нека, например, S е "TOPCODER" и силата на устройството L е 5. Ако момичето ползва устройството в индекс 0, тя ще получи "COOPTDER" тъй като ще сортира "TOPCO" в "COOPT". Ако, обаче, го използва в индекс 2, тя ще сортира "PCODE" в "CDEOP" и ще получи "TOCDEOPR".
За съжаление, нейното устройство има дефект, поради който може да бъде използвано максимум веднъж. Сега момичето се чуди кой е лексикографски най-малкият стринг, който може да получи от S ползвайки го максимум веднъж?
Вход
На първия ред на стандартния вход ще бъдат зададени двете цели числа N и L – съответно дължината на стринга S, с който разполага момичето, и силата на устройството. На следващия ред ще бъде зададен самият стринг S, съдържащ N главни букви от английската азбука ('A'-'Z').
Изход
На стандартния изход изведете един стринг – лексикографски най-малкия резултат, който може да бъде получен ползвайки устройството най-много веднъж.
Ограничения
- 2 ≤ L ≤ N ≤ 50
Примерен Вход | Примерен Изход |
---|---|
8 5 TOPCODER | COOPTDER |
6 3 ESPRIT | EPRSIT |
11 5 ABRACADABRA | AAABCRDABRA |
7 6 BAZINGA | ABGINZA |