A. Today's Word
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have accepted an offer at VortaroEnMano Inc., a company committed to creating the most comprehensive Esperanto dictionary. Esperanto estas tre mojosa lingvo, so you work really hard to do your best – mostly to keep your job in the depression of employment.

Today, you're assigned to refactor the function called "Hodiaŭa Vorto", i.e. "Today's Word" in English. This word is generated from a string, denoted as $$$S_k$$$.

Here's how $$$S_k$$$ is generated:

  1. The process begins with an initial string, $$$S_0$$$, which is given. This string contains only lowercase English letters and has an even length.
  2. For $$$n \ge 1$$$, $$$S_n$$$ is generated in the following way: $$$S_n=S_{n-1}[0\ldots \frac{l}{2}-1]+S_{n-1}+\text{next}(S_{n-1}[\frac{l}{2}\ldots l-1])$$$, where $$$l$$$ is the length of $$$S_{n-1}$$$ and $$$+$$$ is used to concatenate the strings. Note that the index of the string starts from $$$0$$$.

The function $$$\text{next}(S)$$$ increments each character in the string $$$S$$$ to the next letter in the alphabet, i.e., $$$\texttt{a}$$$ changes to $$$\texttt{b}$$$, $$$\texttt{b}$$$ to $$$\texttt{c}$$$, and so on, with $$$\texttt{z}$$$ changing to $$$\texttt{a}$$$. For instance, $$$\text{next}(\texttt{abz})=\texttt{bca}$$$.

Your task is to determine the suffix of $$$S_{10^{100}}$$$ with a length of $$$m$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$), representing the length of $$$S_0$$$ and the length of the desired suffix, respectively. It is guaranteed that $$$n$$$ is an even number.

The second line contains a string, $$$S_0$$$, composed of $$$n$$$ lowercase English letters.

Output

Output a string of length $$$m$$$, which represents the suffix you are tasked to determine.

Example
Input
6 10
bocchi
Output
wrwxrwxsxy
Note

In the provided example, $$$S_1=\underline{\texttt{boc}}\ \underline{\texttt{bocchi}}\ \underline{\texttt{dij}}$$$.