You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一个字符串 $S$ ，现在会对这个字符串进行无限次操作。

每次操作都会生成一个新的字符串 $T$ ，它是将 $S$ 这个字符串的最后一个字符移动到第一个位置得到的，即若

$S=s_1s_2\cdots{s_n}$

则

$T=s_ns_1s_2\cdots{s_{n-1}}$

随后将这个字符串 $T$ 接到字符串 $S$ 的末尾，作为下一次操作的字符串 $S$ 。

现在问进行过无限次操作的字符串 $S$ 的第 $N$ 位是什么字符。

Input Format

输入共两行。

第一行输入一个字符串，保证字符串只包含大写字母，且字符串的长度 $|S|$ 满足 $1 \le |S| \le 30$ 。

第二行输入 $N(1 \le N \le 10^{18})$ ，含义见题目描述（注意，字符串的第一个字符的位置为 $N = 1$ ）。

Output Format

输出一个字符，表示进行过无限次操作的字符串 $S$ 的第 $N$ 位的字符。

NEXT
11​

E​

Hint

NEXT先进行一次操作，得到新的字符串为NEXTTNEX。

NEXTTNEX再进行一次操作，得到新的字符串为NEXTTNEXXNEXTTNE。

可以得知该字符串的第 $11$ 位为E，且经过无限次操作的字符串的第 $11$ 位也为E。