시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.1 초 256 MB38363294.118%

문제

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

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2016 D번

  • 빠진 조건을 찾은 사람: doju