题目描述

给定一个字符串 $s$，定义一个操作 $F(s)$，它将字符串 $s$ 右旋转后追加到自身末尾。

右旋转操作：字符串 $s$ 的最后一个字符成为新字符串的第一个字符，其余字符顺序保持不变。

从初始字符串 $s$ 开始，通过反复应用 $F$ 操作，生成一个无限长度的字符串。每次操作都将字符串的长度加倍。

现在，给定一个初始字符串 $s$ 和一个索引 $N$，请计算在生成的无限字符串中，第 $N$ 个位置上的字符是什么。字符的索引从 $1$ 开始计数。

输入格式

输入为一行，包含一个字符串 $s$，接着是一个整数 $N$，两者由空格分隔。字符串最多包含 30 个大写字母，且 $N \leq 10^{18}$。

输出格式

输出无限字符串中第 $N$ 个位置的字符。

样例 #1

样例输入 #1

NUAA 10

样例输出 #1

N

提示

注意 $N$ 可能太大，无法适应标准的 32 位整数，因此你可能需要使用 64 位整数类型（例如 C/C++ 中的 “long long”）。

在样例中，初始字符串 "NUAA" 会通过操作无限扩展为：

NUAA -> NUAAANUA -> NUAAANUAANUAAANU -> ..

索引 $N=10$ 对应的字符是 "N"。