题目描述

小明收到了一段特殊的“压缩电报”。

这段电报由若干组内容组成，每一组都满足下面的形式：

• 先出现一个英文字母；
• 再出现一个正整数，表示这个字母连续重复的次数。

例如：

• A3B2C4 表示展开后是 AAABBCCCC
• x12Y1 表示展开后是 xxxxxxxxxxxxY

现在给定这段压缩后的电报，以及一个整数 k，请你求出展开后的电报中第 k 个字符是什么。

需要注意的是，展开后的电报可能非常长，不能直接真的把它完整展开出来。

输入格式

输入共 2 行。

第 1 行一个字符串 s，表示压缩后的电报。

第 2 行一个整数 k，表示要查询展开后第 k 个字符。

输出格式

输出一行，一个字符，表示展开后的电报中第 k 个字符。

样例

A3B2C4
5

B

x12Y1
10

x

样例说明

对于所有测试数据：

• 1 <= s.length() <= 100000；
• 1 <= k <= 10^9；
• 字母可能是 A 到 Z 或 a 到 z；
• 每组重复次数均在 1 到 10^18 之间；
• 重复次数使用十进制表示，且没有前导零；
• s 严格由“一个英文字母后紧跟一个重复次数”的若干组内容组成；
• 保证 k 不超过展开后电报的总长度。

本题采用 IOI 单点计分方式，共 20 个测试点，每个测试点 5 分。通过一个测试点即可获得该测试点的分数，不设置 subtask。