题目描述

佩奇突然拥有了一个神奇的魔法，可以把一个由数字1到9组成的字符串 $S$ 随着日期进行变换。每次日期改变时，这个字符串会按照以下规则变化：

• $S$ 中的每一个2都会被替换为22；
• $S$ 中的每一个3都会被替换为333；
• $S$ 中的每一个4都会被替换为4444；
• $S$ 中的每一个5都会被替换为55555；
• $S$ 中的每一个6都会被替换为666666；
• $S$ 中的每一个7都会被替换为7777777；
• $S$ 中的每一个8都会被替换为88888888；
• $S$ 中的每一个9都会被替换为999999999；
• $S$ 中的1保持不变。

例如，如果$S$ 是1324，在第二天它将变为1333224444，第三天变为133333333322224444444444444444。

现在佩奇想要知道在经过$5×10^{15}$天之后，字符串中的第$K$个字符是什么。

1214
4

2

【样例1解释】

第一天:1214

第一天过后:12214444

第二天过后:1222214444444444444444

第三天过后:12222222214444444444444444444444444444444444444444444444444444444444444444

在$10^{15}$天过后前5个字符是12222,因为K=4，所以我们需要输出字符2

3
157

3

299792458
9460730472580800

2

提示

• $S$ 的长度在1到100之间（包含边界）。

• $K$ 是一个范围在1到$10^{18}$之间（包含边界）的整数。

• 经过$5×10^{15}$天后的字符串的长度至少是$K$。