Коровы экспериментируют с секретными кодами, и они изобрели метод
для создания строки с бесконечной длиной которая может быть использована
для кодирования.
Пусть дана строка \(s\), назовём \(F(s)\) строку \(s\) за которой идёт строка \(s\)
"циклически сдвинутая" на один символ вправо (последний символ становится
новым первым символом).
По заданной строке \(s\), коровы строят свою строку бесконечной длины повторя применение \(F\);
каждый шаг удваивает длину текущей строки.
Вам дана начальная строка и индекс \(N\), помогите коровам вычислить символ на позиции \(N\),
в этой бесконечной строке.
ФОРМАТ ВВОДА (файл cowcode.in):
Ввод состоит из одной строки, содержащий строку, за которой следует число
\(N\).
Строка содержит не более 30 больших латинских букв,
\(N \leq 10^{18}\).
Заметим, что \(N\) может не поместиться в 32-битное целое, поэтому нужно использовать
64-битное целое (например long long для С/С++).
ФОРМАТ ВЫВОДА (файл cowcode.out):
Выведите \(N\)-ый символ в бесконечной строке построенной по данной. Первый символ
имеет \(N=1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
COW 8
|
C
|