#MX88. Song

Song

题目描述

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

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

现在,你根据压缩后的字符串和一个整数 cc,想知道:如果这段旋律无限循环播放,第 cc 个音符(从第 0 个开始编号)是什么?

输入格式

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

第二行是一个非负整数 cc。

输出格式

输出一个小写字母,表示第 cc 个音符。

数据规模与约定

对于 30%30\% 的数据,满足:

  • 0≤c≤2×1030\le c\le 2\times 10^3;
  • s′s' 中出现的整数的范围是 [1,9][1,9];
  • 压缩前,ss 的长度不超过 20002000。

对于 50%50\% 的数据,满足:

  • 0≤c≤1060\le c\le 10^6;

  • 压缩前,ss 的长度不超过 10610^6。

对于 70%70\% 的数据,满足:

  • 压缩前,ss 的长度不超过 10610^6。

对于 100%100\% 的数据,保证:

  • 2≤∣s′∣≤2×1052\le |s'|\le 2\times10^5;
  • s′s' 中出现的整数的范围是 [1,1012][1,10^{12}];
  • 0≤c≤10120\le c\le 10^{12}。

样例 1 输入

r2d2
8

样例 1 输出

r

样例 2 输入

a4b1c2d10
100

样例 2 输出

d

输入/输出样例3

见下发文件。