Drawn and Quartered

Interview

Time limit2sMemory limit512 MB

Summary

A fixed permutation is applied to a string K times; find where each index goes and output the rearranged string.

Level: Medium6 of 10
Topics: Math, Bit manipulation, Recursion
Solved: No attempts yet

Problem

You are playing a game that involves drawing and redrawing a string on a blackboard. You start with a string $S$ of length $N$ and perform a switcheroo on the string exactly $K$ times. A switcheroo involves breaking $S$ into quarters, and then moving the middle two quarters to the end of $S$ without changing their relative order to each other. For example, say you start with aabbccdd. After a single switcheroo, the string becomes aaddbbcc. After another switcheroo, you have aaccddbb, and so on.

Given a starting string $S$ and the number of times you should perform a switcheroo, what is the final state of the string?

Input

The input starts with a line containing two integers $N$ ( $4 \le N \le 100\,000$ ), the length of the string, and $K$ ( $1 \le K \le 10^{18}$ ), the number of times you should perform a switcheroo on $S$ . It is guaranteed that $N$ is a multiple of 4.

The second line contains $S$ . The string $S$ contains only lowercase letters and consists of exactly $N$ characters.

Output

Display the string after performing $K$ switcheroos.

Examples3

Example 1
Input
```
4 2
abcd
```
Expected output
```
acdb
```
Example 2
Input
```
8 1
abcdefgh
```
Expected output
```
abghcdef
```

Example 3

Input

20 26
southpacificregional

Expected output

southicregionalpacif