题目描述

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

给定一个字符串${s，}$让 ${F(s)}$为 ${s }$后跟 ${s}$向右"旋转"一个字符（在向右旋转中，${s }$的最后 一个字符旋转并成为新的第一个字符）拼接得到。

给定一个初始字符串${s，}$奶牛通过重复应用${F }$来构建它们的无限长代码字符串；因此，每一步都会使当前字符串的长 度加倍。

给定初始字符串和索引${N，}$请帮助奶牛计算无限代码字符串中第${N }$个位置的字符。

输入格式

输入由一行组成，其中包含一个字符串，后跟${N}$。字符串最多由${30}$个大写字符组成，并且

${N≤}$${10^{18}}$

注意，神经网络可能太大，无法容纳标准的${32}$位整数，因此您可能希望使用${64}$位整数类型（例如，${C/C++}$中的"${long-long}$"）。

输出格式

请输出由初始字符串生成的无限代码的第${n}$个字符。

第一个字符是${N=1}$

样例

输入样例

COW 8

输出样例

C

提示

在本例中，初始字符串${COW}$展开如下：

COW -> COWWCO -> COWWCOOCOWWC
12345678