Problem Statement

Given a string $s$, define an operation $F(s)$ that appends a right rotation of string $s$ to the end of itself.

Right rotation means that the last character of $s$ becomes the first character of the new string, while the remaining characters retain their original order.

Starting from the initial string $s$, by repeatedly applying the $F$ operation, an infinite-length string is generated. Each operation doubles the length of the string.

Given the initial string $s$ and an index $N$, find the character at the $N^{th}$ position in the infinitely generated string. The index $N$ is 1-based.

Input

The input consists of a single line containing a string $s$, followed by an integer $N$, separated by a space. The string contains up to 30 uppercase letters, and $N \leq 10^{18}$.

Output

Output the character at the $N^{th}$ position in the infinite string.

Example

Input

NUAA 10

Output

N

Explanation

Note that $N$ can be very large, beyond the range of standard 32-bit integers, so you may need to use a 64-bit integer type (such as "long long" in C/C++).

In this example, the initial string "NUAA" expands infinitely as follows:

NUAA -> NUAAANUA -> NUAAANUAANUAAANU -> ..

The character at index $N=10$ is "N".