#UM103. USACO17JAN Secret Cow Code S

USACO17JAN Secret Cow Code S

奶牛们正在试验秘密密码,并设计了一种方法来创建一个无限长的字符串,作为其密码的一部分。

给定一个字符串 ss,F(s)F(s) 操作是指将 ss 与 s’s’ 拼接起来,组成新的字符串,其中 s’s’ 是将 ss 的最后一个字符移动到最前面后形成的字符串。

例如,当 ss 为 ABCD 时,s’s’ 为 DABC,拼接而成的新字符串为 ABCDDABC。

不断重复 FF 操作,可以使得字符串无限延长,每次操作都会使当前字符串的长度加倍。

给定初始字符串和整数 NN,请你求出无限延伸的字符串中第 NN 个字符是什么。

输入格式

输入共一行,包含一个由大写字母构成的字符串以及一个整数 NN。

输出格式

输出由初始字符串构建的无限字符串中的第 NN 个字符。

NN 从 11 开始计数。

数据范围

给定字符串长度不超过 3030,
1≤N≤10181 \le N \le 10^{18},
注意,NN 可能超过标准的 3232 位整数型能够表示的范围,所以你可能需要使用更大的数据类型,例如C/C++中的“long long”。

输入样例:

COW 8

输出样例:

C

样例解释

在此样例中,初始字符串 COW 的扩展如下:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678