Reading Digits

Time limit0.1sMemory limit256 MB

Summary

Decode the given run-length-encoded string k times, then report the digit at index pos of the original string s.

Level: Medium7 of 10
Topics: String, Implementation, Recursion
Solved: No attempts yet

Problem

Bob encodes strings of digits in his own way. He reads "1211" as one 1, one 2, two 1s, which gives "111221". Applying the same rule once more gives "312211", and that string is the result of encoding "1211" two times.

You are given the result of encoding a string $s$ exactly $k$ times. The string $s$ contains only non-zero digits, that is digits from 1 to 9, and no digit repeats 10 or more times in a row. Find the digit at position $pos$ of $s$ , counting from 0.

Input

The first line contains $k$ and $pos$ , separated by a space. The second line contains the string obtained by encoding $s$ exactly $k$ times.

$1 \le k \le 39$ , $0 \le pos \le 100000$ , and $pos < |s| \le 200000$ .

Output

Print the digit at position $pos$ of $s$ .

Examples6

Example 1
Input
```
2 0
312211
```
Expected output
```
1
```
Example 2
Input
```
2 1
312211
```
Expected output
```
2
```
Example 3
Input
```
1 3
312211
```
Expected output
```
2
```
Example 4
Input
```
3 0
1321123113
```
Expected output
```
1
```
Example 5
Input
```
3 1
1321123113
```
Expected output
```
2
```
Example 6
Input
```
3 2
1321123113
```
Expected output
```
3
```