시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.1 초 256 MB 17 15 13 86.667%

문제

Bob has a very special way of encoding strings formed with digits. For instance, he encodes “1211” as: “one of one, one of two, two of one”, or, more precisely: “111221”. Bob’s encoding of the latter string is: “312211”. We call this a “two-times re-encoding of 1211”. Bob likes repeating this process several times.

You are given a string of digits which represents the “kth re-encoding of a string s”. The string s contains only non-zero digits (i.e. [1-9]). Also, it is not possible to have a sequence of more than 9 repeating digits in s. You must find the digit which lays on the pos position (starting from 0) of the string s.

입력

The input consists of two lines. The first line contains the values k and pos. The second line contains the k th re-encoding of s. We have 1 < k < 40, 0 ≤ pos ≤ 100000, and pos < |s| ≤ 200000.

출력

The output is the digit from position pos of s.

예제 입력 1

2 0
312211

예제 출력 1

1

예제 입력 2

2 1
312211

예제 출력 2

2

예제 입력 3

1 3
312211

예제 출력 3

2

예제 입력 4

3 0
1321123113

예제 출력 4

1

예제 입력 5

3 1
1321123113

예제 출력 5

2

예제 입력 6

3 2
1321123113

예제 출력 6

3

힌트