Secret Cow Code

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string s, let F(s) be s followed by s "rotated" one character to the right (in a right rotation, the last character of s rotates around and becomes the new first character). Given an initial string s, the cows build their infinite-length code string by repeatedly applying F; each step therefore doubles the length of the current string.

Given the initial string and an index n, please help the cows compute the character at the n-th position within the infinite code string.

Input

Consists of a single line containing a string followed by n (n ≤ 10^18). The string consists of at most 30 uppercase characters.

Output

Print the n-th character of the infinite code built from the initial string. The first character is n = 1.

Examples

Note

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC
                 12345678