Magical Runes

Time limit1sMemory limit1024 MB

Summary

Given a string S of A and B runes and a day count D below 2^30, the task is to print the rune states after D days.

Level: Medium4 of 10
Topics: Bit manipulation, Implementation
Solved: No attempts yet

Problem

You maintain a very nice collection of magical runes. They generally come in two types, type A and type B. You have arranged your runes on a shelf. Each day the runes change. At the start of each day, the leftmost rune switches its type (from A to B or from B to A). Every other rune changes only if the rune to its left changes from B to A. For example, if three runes start as ABBAA, then at the start of the next day only the leftmost rune changes, and the sequence becomes BBBAA. After another day, the leftmost rune changes, then the second rune changes because its left neighbor changed from B to A, and then the third and fourth runes change for the same reason. After those changes, the runes look like AAABA.

Your task is to find the states of the runes after $D$ days, given that they start in state $S$ . The rightmost rune never changes from B to A at the start of any of the $D$ days you are asked to consider.

Input

The input is a single line containing a string $S$ followed by an integer $D$ . The length of $S$ is between 1 and 30 inclusive, and $S$ consists only of the characters A and B. The value $D$ satisfies $0 \le D < 2^{30}$ .

Output

Print a single string showing the states of the runes after $D$ days have elapsed, starting from state $S$ .

Examples3

Example 1
Input
```
ABBAA 2
```
Expected output
```
AAABA
```
Example 2
Input
```
ABAA 4
```
Expected output
```
ABBA
```

Example 3

Input

ABBABBABBABBABBABBABBABBABBABA 536870912

Expected output

ABBABBABBABBABBABBABBABBABBABB