Problem C
Evolving Etymology
Eelco has recently started to gain interest in the field that studies the origin of words: etymology. He especially likes how words can evolve in many different ways: pronunciation changes over time, words are borrowed from different languages, and the meaning of words can change based on culture. Eelco is eager to attend the Networking With Etymologists: Revolutionary Conference for the first time ever. To make a good first impression, he is going to present a completely new method to make new words from existing words.
To make a new word from an existing word $s$, Eelco proposes to take every second letter of $s+s$, starting with the first letter. For example, applying this method to the word “etymology” would result in “eyooytmlg”. Of course, to design even more words, this process can be repeated many times. Eelco would like to prepare a list of new words to present at the conference, so he writes a program that applies his method some predetermined number of times.
Input
The input consists of:
-
One line with two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 10^{18}$), the length of the original word and the number of times to apply the method.
-
One line with a string $s$ of length $n$, only consisting of English lowercase letters (a-z), the original word.
Output
Output the resulting word after applying the method to the original word $k$ times.
| Sample Input 1 | Sample Output 1 |
|---|---|
9 1 etymology |
eyooytmlg |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 1 word |
wrwr |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1000000000000000000 delft |
delft |
| Sample Input 4 | Sample Output 4 |
|---|---|
5 5 eceol |
eelco |
