奶牛们正在实验秘密代码，并设计了一种方法用于生成无限长度的字符串，作为他们代码的一部分。

给定一个字符串 s，令 F(s) 为 s 后接 s 向右“旋转”一个字符的结果（在右旋转中，s 的最后一个字符旋转并成为新的第一个字符）。给定初始字符串 s，奶牛们通过重复应用 F 来构建他们的无限长度代码字符串；因此每一步都会使当前字符串的长度翻倍。

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

第一行输入一个字符串。该字符串包含最多 30 个大写字母，数据保证 N≤10^18。

第二行输入 一个整数 N。请注意，数据可能很大，放进一个标准的 32 位整数容器可能不够，所以你可能要使用一个 64 位的整数容器（例如，在 C/C++ 中是 long long）。

请输出从初始字符串生成的无限字符串中的下标为 N 的字符。第一个字符的下标是 N=1。

【样例说明】

样例中，初始字符串 COW 扩展如下： COW -> COWWCO -> COWWCOOCOWWC（第8个字母）

递归分治