题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

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

样例

输入样例

COW 8

输出样例

C

提示

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

COW -> COWWCO -> COWWCOOCOWWC
12345678