旋律压缩

题目描述

你正在看一部非常长的动画番剧，但片头曲每集都一样。你实在太熟悉这段旋律了，甚至能在心里无限循环地哼唱出来。

为了节省内存，你决定将这段旋律压缩储存：对于连续相同的音符，只保留这个音符和它连续出现的次数。比如旋律 aaaabccdddd 会被压缩成 a4b1c2d4，表示有 4 个 a ，1 个 b ，2 个 c ，4 个 d 。

现在，你根据压缩后的字符串和一个整数 $c$，想知道：如果这段旋律无限循环播放，第 $c$ 个音符（从第 0 个开始编号）是什么？

输入格式

第一行是一个只包含小写字母和数字的压缩旋律字符串 $s’$。

第二行是一个非负整数 $c$。

输出格式

输出一个小写字母，表示第 $c$ 个音符。

数据范围

对于 $30\%$ 的数据，满足：

• $0\le c\le 2\times 10^3$；
• $s'$ 中出现的整数的范围是 $[1,9]$；
• 压缩前，$s$ 的长度不超过 $2000$。

对于 $50\%$ 的数据，满足：

• $0\le c\le 10^6$；

• 压缩前，$s$ 的长度不超过 $10^6$。

对于 $70\%$ 的数据，满足：

• 压缩前，$s$ 的长度不超过 $10^6$。

对于 $100\%$ 的数据，保证：

• $2\le |s'|\le 2\times10^5$；
• $s'$ 中出现的整数的范围是 $[1,10^{12}]$；
• $0\le c\le 10^{12}$。

输入输出样例

输入样例1

r2d2
8

输出样例1

r

输入样例2

a4b1c2d10
100

输出样例2

d

输入/输出样例3

见下发文件。

下发数据

• 下载 song3.in
• 下载 song3.out