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

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

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

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

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

输入格式

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

输出格式

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

$N$ 从 $1$ 开始计数。

数据范围

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

输入样例：

COW 8

输出样例：

C

样例解释

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

COW -> COWWCO -> COWWCOOCOWWC
                 12345678