Секретный коровий код

Коровы экспериментируют с секретными кодами, и они изобрели метод для создания строки с бесконечной длиной которая может быть использована для кодирования.

Пусть дана строка s, назовём F(s) строку s за которой идёт строка s "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке s, коровы строят свою строку бесконечной длины повторя применение F; каждый шаг удваивает длину текущей строки.

Вам дана начальная строка и индекс n, помогите коровам вычислить символ на позиции n в этой бесконечной строке.

Входные данные

Содержит строку, за которой следует число n (n ≤ 10^18). Строка содержит не более 30 больших латинских букв.

Выходные данные

Выведите n-ый символ в бесконечной строке построенной по данной. Для первого символа n = 1.

Примеры

Примечание

В нашем примере изначальная строка COW расширяется следующим образом:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678