H. Shuffling Cards with Problem Solver 68!time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAru loves playing card games (Poker, Texas hold 'em, Balatro, etc.) and she has perfected the art of shuffling cards, especially the riffle shuffle. She is playing with Mutsuki now, and it's her turn to shuffle the cards!However, Mutsuki knows that Aru is too perfect with her shuffling game. In fact, given a deck with an even number of cards, Aru always performs a perfect riffle: she cuts the deck evenly and interleaves the two halves. Formally, if the deck is represented by a string $$$s$$$ of length $$$n$$$, where $$$s_i$$$ is the $$$i$$$-th card from the top, one riffle produces the deck $$$$$$s^\prime = s_1 + s_{n/2 + 1} + s_2 + s_{n/2 + 2} + \ldots + s_{n/2} + s_{n}.$$$$$$ Mutsuki also knows that when handed a deck of cards, Aru will riffle it exactly $$$t$$$ times.Mutsuki currently holds a deck of $$$2^k$$$ cards, represented by a string $$$d$$$. Before giving the deck to Aru, Mutsuki can choose to cut the deck, by moving some number of cards from the top to the bottom of the deck. Formally, she can choose any $$$m$$$ from $$$0$$$ to $$$2^k - 1$$$, and produce the deck $$$$$$d^\prime = d_{m + 1} + d_{m + 2} + \ldots + d_{2^k} + d_1 + d_2 + \ldots + d_m.$$$$$$Among all $$$2^k$$$ possible cuts, Mutsuki wants to choose the one that results in the lexicographically smallest deck after Aru riffles it $$$t$$$ times. Can you figure this out for her?InputThe first line contains two integers $$$k$$$ and $$$t$$$, representing the size parameter of the deck, and the number of times Aru will riffle the deck, respectively.The second line contains a string $$$d$$$ of $$$2^k$$$ lowercase characters, representing the original deck of cards that Mutsuki has. $$$1 \le k \le 18$$$ $$$0 \le t \le 10^9$$$ OutputPrint a string in one line, representing the lexicographically smallest deck of cards that Mutsuki can produce, by first cutting the deck and letting Aru riffle it $$$t$$$ times.ExamplesInput4 2
baaabaaabaaabaaa
Outputaaaaaaaaaaaabbbb
Input4 999999999
abcdefghijklmnop
Outputacegikmobdfhjlnp
Input4 17
bbcttckrdezzzbcd
Outputbcckdrbdbecztztz