题目描述

奶牛们设计了一种生成无限长字符串的方法，给定初始大写英文字母字符串$s$，定义$F(s)$操作：将$s$与$s'$拼接为新字符串，其中$s'$是把$s$的最后一个字符移到最前面形成的字符串。不断重复$F(s)$操作可让字符串无限延长，且每次操作后字符串长度加倍。

给定初始字符串和整数$N$（字符位置从1开始计数），请求出无限延伸的字符串中第$N$个字符。

输入格式

一行包含一个大写英文字母字符串和一个整数$N$，二者以空格分隔。 字符串长度不超过30，且$1≤N≤10^{18}$。

输出格式

一行一个字符，表示无限字符串中第$N$个字符。

样例输入

COW 8

样例输出

C

样例解释

初始字符串为COW，经2次$F$操作后得到字符串COWWCOOCOWWC（长度12），该字符串的第8位字符为$C$，即为答案。