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

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

1 секунда

128 мегабайтів

Середня

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

Для заданого рядка $s$ визначимо $F (s)$ як конкатенацію рядка $s$ та копії рядка $s$ , циклічно зсунутої на один символ вправо. При циклічному зсуві вправо останній символ рядка $s$ переміщується на початок, а всі інші символи зсуваються на одну позицію вправо.

Починаючи з вихідного рядка $s$ , корови будують свій нескінченний кодовий рядок, багаторазово застосовуючи операцію $F$ . Кожне застосування $F$ подвоює довжину поточного рядка.

За вихідним рядком та індексом $n$ допоможіть коровам визначити символ, що знаходиться на $n$ -й позиції отриманого нескінченного рядка.

Вхідні дані

Містить рядок, за яким слідує число $n (n \leq 1 0^{18})$ n~(n \le 10^{18}). Рядок складається не більш ніж із $30$ великих англійських літер.

Вихідні дані

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

Приклади

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

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

Приклад 1