Migrated from Lutece 2313 Sugarii and String

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Sugarii is very good at solving string problems. One day, a string $S$ suddenly comes to his mind. It is a string with $n$ digits and consists of only $0$ and $1$. Then he figures out a way to make it longer with the following steps:

1. Copy $S$ to a new string $T$.
2. Reverse every digit in $T$. That is, for every digit in $T$, if it's $0$, change it to $1$; if it's $1$, change it to $0$.
3. Append $T$ to the end of $S$.
4. Go back to step 1.

For example, if $S$ is initially $110$, then it becomes $110001$, and then $110001001110$, and then $110001001110001110110001$... The final string can be as long as you want. Sugarii wants to know whether the $k$-th digit of the final string is $0$ or $1$.

Input

The first line contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le {10}^{18}$) — the length of string $S$ and the digit Sugarii wants to know.

The second line contains a string $S$, consisting of $0$ and $1$.

Output

Print the $k$-th digit of the final string ($0$ or $1$).

Samples

3 5
110

0

1 10
1

1

Note

In the first sample, the final string is $110001001110001110110001$... , the 5th digit is $0$.

In the second sample, the final string is $1001011001101001$... , the 10th digit is $1$.

Resources

电子科技大学第十一届 ACM 趣味程序设计竞赛