Problem D
Magical Runes
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 to show them off. Because they are magical runes, they change each day. That is, at the start of each day the leftmost rune will switch its type (i.e. from A to B or from B to A, depending on its type just before the start of the day). Every other rune will only change if the type of the rune to its left changes from B to A.
For example, if you have three runes initially arranged like ABBAA, then at the start of the next day only the leftmost rune will change and the sequence will look like BBBAA. After another day, the leftmost rune will change, but then the second rune from the left will change because the rune beside it changed from B to A. But then the third rune will also change for the same reason. And then the fourth rune will also change! That is, after the changes at the start of this day the runes will look like AAABA.
Your task is the following. Given the initial states $S$ of an initial arrangement of runes and given a number of days $D$, you should determine the states of the runes after $D$ days have elapsed.
Input
Input consists of a single line that first begins with a string $S$ followed by an integer $D$. The length of $S$ will be between $1$ and $30$ (inclusive) and $S$ will consist only of characters A and B. The value $D$ satisfies $0 \leq D < 2^{30}$.
Finally, you are also guaranteed that the rightmost rune does not change from B to A at the start of any of the $D$ days that you are to consider.
Output
Display a single string showing the states of the runes after $D$ days have elapsed, given they started in state $S$.
| Sample Input 1 | Sample Output 1 |
|---|---|
ABBAA 2 |
AAABA |
| Sample Input 2 | Sample Output 2 |
|---|---|
ABAA 4 |
ABBA |
| Sample Input 3 | Sample Output 3 |
|---|---|
ABBABBABBABBABBABBABBABBABBABA 536870912 |
ABBABBABBABBABBABBABBABBABBABB |
