Секретний коров'ячий код

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

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

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

Вам дано початковий рядок і індекс n. Допоможіть коровам обчислити символ на позиції n у цьому нескінченному рядку.

Вхідні дані

Містять рядок, за яким слідує число n (n ≤ 10^18). Рядок містить не більше 30 великих латинських літер.

Вихідні дані

Виведіть n-ий символ у нескінченному рядку, побудованому за даним. Для першого символу n = 1.

Приклади

Вхідні дані #1

Відповідь #1

Примітка

У нашому прикладі початковий рядок COW розширюється наступним чином:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

Відправки 40

Коефіцієнт прийняття 33%