C - To Infinity /

﻿配点: 300

問題文

Mr. Infinity は, 1 から 9 までの数字からなる文字列 S を持っている. この文字列は, 日付が変わるたびに次のように変化する.

• 文字列 S に含まれるそれぞれの 222, 3333, 44444, 555555, 6666666, 77777777, 888888888, 9999999999 に置き換わる. 11 のまま残る.

あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K 文字目は何か？

制約

• S1 文字以上 100 文字以下の文字列.
• K1 以上 10^{18} 以下の整数.
• 5000 兆日後の文字列の長さは K 文字以上である.

入力

S
K


出力

5000 兆日後に Mr. Infinity が持っている文字列の K 文字目の数字を出力しなさい.

入力例 1

1214
4


出力例 1

2


• 現在: 1214
• 1 日後: 12214444
• 2 日後: 1222214444444444444444
• 3 日後: 12222222214444444444444444444444444444444444444444444444444444444444444444

5000 兆日後の文字列の最初 5 文字は 12222 となる. K=4 なので, 4 文字目の 2 を出力すればよい.

入力例 2

3
157


出力例 2

3


入力例 3

299792458
9460730472580800


出力例 3

2


﻿Score: 300 points

Problem Statement

Mr. Infinity has a string S consisting of digits from 1 to 9. Each time the date changes, this string changes as follows:

• Each occurrence of 2 in S is replaced with 22. Similarly, each 3 becomes 333, 4 becomes 4444, 5 becomes 55555, 6 becomes 666666, 7 becomes 7777777, 8 becomes 88888888 and 9 becomes 999999999. 1 remains as 1.

For example, if S is 1324, it becomes 1333224444 the next day, and it becomes 133333333322224444444444444444 the day after next. You are interested in what the string looks like after 5 \times 10^{15} days. What is the K-th character from the left in the string after 5 \times 10^{15} days?

Constraints

• S is a string of length between 1 and 100 (inclusive).
• K is an integer between 1 and 10^{18} (inclusive).
• The length of the string after 5 \times 10^{15} days is at least K.

Input

Input is given from Standard Input in the following format:

S
K


Output

Print the K-th character from the left in Mr. Infinity's string after 5 \times 10^{15} days.

Sample Input 1

1214
4


Sample Output 1

2


The string S changes as follows:

• Now: 1214
• After one day: 12214444
• After two days: 1222214444444444444444
• After three days: 12222222214444444444444444444444444444444444444444444444444444444444444444

The first five characters in the string after 5 \times 10^{15} days is 12222. As K=4, we should print the fourth character, 2.

Sample Input 2

3
157


Sample Output 2

3


The initial string is 3. The string after 5 \times 10^{15} days consists only of 3.

Sample Input 3

299792458
9460730472580800


Sample Output 3

2