Given a string $S = s_1 s_2 \cdots s_{n-1} s_n$, we can perform a circular left shift to obtain the new string $S' = s_2 s_3 \cdots s_n s_1$. We can perform yet another circular left shift to get $S'' = s_3 \cdots s_n s_1 s_2$.

For example, the first few circular left shifts for the string abcde would be $$abcde \to \underset{k=1}{bcdea} \to \underset{k=2}{cdeab}$$

What will $S$ look like after we perform $k$ circular left shifts?

Input

The first line of input contains the string $S$.
The second line of input contains an integer $k$.

Output

Output the resulting string after performing $k$ circular left shifts on $S$.

Constraints

For all subtasks, $2 \le |S|, k \le 10^6$. $S$ consists of lowercase English letters only.
Subtask 1 (40%): $1 \le k < |S| \le 1000$
Subtask 2 (60%): No additional constraints.