Secret Cow Code#10549

Secret Cow Code

1 second

128 megabytes

Medium

The cows are experimenting with secret codes and have devised a method for generating an infinite string to use as part of one of their codes.

Given a string $s$ , let $F (s)$ be the concatenation of $s$ and a copy of $s$ rotated one character to the right. In a right rotation, the last character of $s$ moves to the beginning, and all other characters shift one position to the right.

Starting with an initial string $s$ , the cows construct their infinite code string by repeatedly applying $F$ . Each application of $F$ doubles the length of the current string.

Given the initial string and an index $n$ , help the cows determine the character at the $n$ -th position of the resulting infinite code string.

Input

Consists of one line containing a string followed by $n (n \leq 1 0^{18})$ n~(n \le 10^{18}). The string consists of at most $30$ uppercase English letters.

Output

Print the $n$ -th character of the infinite code string generated from the initial string. The first character is at position $1$ .

Examples

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

COW -> COWWCO -> COWWCOOCOWWC
                 12345678

Example 1