Evolving Etymology

Interview

Time limit1sMemory limit1024 MB

Summary

Given a word s of length n, apply the every-second-letter transform k times (k up to 10^18) and print the resulting word.

Level: Medium5 of 10
Topics: Math, Number theory, String
Solved: No attempts yet

Problem

Eelco has recently become interested in etymology, the study of where words come from. He especially likes how words change over time: pronunciation shifts, words are borrowed from other languages, and meanings change with culture. Eelco is attending the Networking With Etymologists: Revolutionary Conference for the first time. To make a good first impression, he will present a new method for making words from existing words.

To make a new word from an existing word $s$ , take every second letter of $s+s$ , starting with the first letter. For example, applying this method to the word etymology gives eyooytmlg. The process can be repeated many times. Eelco wants a list of new words for the conference, so he is writing a program that applies the method a fixed number of times.

Input

The first line contains 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.

The second line contains a string $s$ of length $n$ , consisting only of lowercase English letters (a-z), the original word.

Output

Print the resulting word after applying the method to the original word $k$ times.

Examples4

Example 1
Input
```
9 1
etymology
```
Expected output
```
eyooytmlg
```
Example 2
Input
```
4 1
word
```
Expected output
```
wrwr
```
Example 3
Input
```
5 1000000000000000000
delft
```
Expected output
```
delft
```
Example 4
Input
```
5 5
eceol
```
Expected output
```
eelco
```