# Problem F

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 |