시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB75574882.759%

문제

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 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≤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.

출력

Display a single string showing the states of the runes after $D$ days have elapsed, given they started in state $S$.

예제 입력 1

ABBAA 2

예제 출력 1

AAABA

예제 입력 2

ABAA 4

예제 출력 2

ABBA

예제 입력 3

ABBABBABBABBABBABBABBABBABBABA 536870912

예제 출력 3

ABBABBABBABBABBABBABBABBABBABB

출처

University > University of Alberta Programming Contest > UAPC 2022 F번

  • 문제를 만든 사람: Jiacheng Wu