Bajtosia works in the most modern biological laboratory in all of Byteland. Her team is studying a new species of virus. The team members have determined that the genotype of this virus consists only of two types of genes, which we will denote with the characters 0 and 1. The genotype consists of exactly $n$ such genes. The entire genotype can therefore be described by a sequence $(X_1, X_2, \dots, X_n)$, where each element is the character 0 or 1.

Unfortunately, it turned out that this virus mutates in a very specific but regular way. Every day, the first gene on the left ($X_1$) detaches, changes into the gene $X_1 \oplus X_2$ ($\oplus$ denotes the XOR operation, i.e., exclusive OR*), and then attaches to the right side of the genotype. Thus, the genotype $(X_1, X_2, \dots, X_n)$ after the first mutation will have the form $(X_2, X_3, \dots, X_n, X_1 \oplus X_2)$.

Bajtosia now needs to find out what the virus's genotype will look like after $d$ days. Are you able to help her with this?

Input

The first line of input contains two integers $n$ and $d$ ($2 \leq n \leq 700$, $1 \leq d \leq 10^{15}$), representing the length of the genotype and the number of days the virus will undergo mutations, respectively.

The second and final line contains a description of the original virus genotype in the format of a string consisting of $n$ characters $X_1, X_2, \dots, X_n$ ($X_i \in \{0, 1\}$); the $i$-th character denotes the type of the $i$-th gene of the virus.

Output

Output a single line containing the virus genotype after $d$ days, in the form of a string consisting of $n$ characters in the same format as the input.

Examples

Input 1

5 4
01010

Output 1

01111

Note

Explanation of the example: The virus genotype on consecutive days looks as follows: $01010 \to 10101 \to 01011 \to 10111 \to 01111$.

Subtasks

*The result of this logical operation is 1 when the two arguments are different, or 0 if they are the same. Thus $0 \oplus 1 = 1 \oplus 0 = 1$, while $0 \oplus 0 = 1 \oplus 1 = 0$.