配点: $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$ 文字目の数字を出力しなさい.

1214
4

2

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

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

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

3
157

3

文字列ははじめ 3 である. $5000$ 兆日経ったとき, 文字列は 3 だけで構成される.

299792458
9460730472580800

2