C - To Infinity Editorial /

Time Limit: 2 sec / Memory Limit: 976 MB

配点: 300 点

問題文

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

  • 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666666, 7 が 7777777, 8 が 88888888, 9 が 999999999 に置き換わる. 1 は 1 のまま残る.

例えば, S が 1324 の場合, 翌日には 1333224444 になり, 翌々日には 133333333322224444444444444444 になる.
あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K 文字目は何か？

制約

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

入力

入力は以下の形式で標準入力から与えられる. 

S
K

出力

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

入力例 1

1214
4

出力例 1

2

文字列 S は次のように変化していく.

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

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

入力例 2

3
157

出力例 2

3

文字列ははじめ 3 である. 5000 兆日経ったとき, 文字列は 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