Коровы экспериментируют с секретными кодами, и они изобрели метод для создания строки с бесконечной длиной которая может быть использована для кодирования.
Пусть дана строка s, назовём F(s) строку s за которой идёт строка s "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке s, коровы строят свою строку бесконечной длины повторя применение F; каждый шаг удваивает длину текущей строки.
Вам дана начальная строка и индекс n, помогите коровам вычислить символ на позиции n в этой бесконечной строке.
Содержит строку, за которой следует число n (n ≤ 10^18
). Строка содержит не более 30 больших латинских букв.
Выведите n-ый символ в бесконечной строке построенной по данной. Для первого символа n = 1.
В нашем примере изначальная строка COW расширяется следующим образом: