Kiên và xâu

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 500M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Kiên có một xâu ~S~ độ dài ~N~ gồm các ký tự in thường. Kiên rất thích chữ ~K~ nên Kiên sẽ thực hiện biến đổi xâu ~S~ đúng ~K~ lần. Tại mỗi bước biến đổi Kiên thực hiện như sau:

  • Gọi ~X~ là xâu đảo ngược của xâu ~S~, ~Y=S+X~
  • Chọn một xâu con ~Z~ độ dài ~N~ của ~Y~ và gán ~S=Z~

Trong tất cả các cách biến đổi để đạt được xâu ~S~ cuối cùng, hãy giúp Kiên tìm được xâu có thứ tự từ điển nhỏ nhất.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N (1 \leq N \leq 5000)~ và ~K (1 \leq K \leq 10^{9})~. Dòng thứ hai chứa xâu ~S~

Output

In ra một dòng duy nhất chứa xâu có thứ tự từ điển nhỏ nhất có thể biến đổi được từ ~S~ sau đúng ~K~ bước.

Sample Input 1

5 2
abcba

Sample Output 1

aaaab

Sample Input 2

5 3
acacc

Sample Output 2

aaaac

Comments

Please read the guidelines before commenting.