O Yeongsik's Treasure

O Yeongsik's treasure is a model of the Tower of Hanoi. The tower has three pegs named A, B, and C from left to right, and N disks whose sizes are numbered from 1 to N. Initially all disks are on peg A. A larger disk must always be below a smaller disk on the same peg, so disk N starts at the bottom and disk 1 starts at the top. Each move transfers exactly one disk.

Minsik wants to play with Yeongsik by moving the tower. They have already played the usual game of moving every disk from A to C many times, so Dasom suggests a new rule. First, Dasom shows a valid state that can be reached by following the rules. Starting from the initial state, consider a shortest sequence of moves that reaches that state. Write a program that prints the tower state after exactly M moves in that shortest sequence.

The first line contains the number of disks N and the number of moves M to perform. The second line contains the target state shown by Dasom as a string. Every character is one of A, B, and C. The first character gives the peg containing disk 1, the second character gives the peg containing disk 2, and in general the i-th character gives the peg containing disk i+1.

N is a positive integer no greater than 30. M is an integer satisfying 0 <= M <= m, where m is the minimum number of moves needed to reach the given state from the initial state.

Print one line containing the tower state in the same format as the input state.

For N=3 and target CCC, the shortest sequence from AAA to CCC is AAA -> CAA -> CBA -> BBA -> BBC -> ABC -> ACC -> CCC.