题目描述

农场里的牛群正在研究一种秘密密码编码方式。它们发明了一种从初始字符串构造无限长密码串的方法。

给定一个字符串 $s$，定义 $F(s)$ 为 $s$ 拼接上 $s$ 的循环右移结果（即 $s$ 的最后一个字符移到最前面）。从初始字符串 $s$ 出发，牛群不断对当前字符串施加 $F$ 操作来生成无限长的密码串，每次操作后字符串长度翻倍。

给定初始字符串和一个位置编号 $N$，请帮牛群找出无限密码串中第 $N$ 个位置的字符。

输入格式

输入一行，包含一个字符串和一个整数 $N$，中间用空格分隔。字符串由至多 $30$ 个大写字母组成，$N \le 10^{18}$。

注意 $N$ 可能超出 $32$ 位整数范围，请使用 $64$ 位整数类型（如 C/C++ 中的 long long）。

输出格式

输出无限密码串中第 $N$ 个位置的字符。第一个字符对应 $N = 1$。

样例

COW 8

C

提示

样例 1 解释

初始字符串 COW 的展开过程如下：

COW → COWWCO → COWWCOOCOWWC

前 $8$ 个字符为 COWWCOOC，第 $8$ 个字符是 C。