오영식의 보물

오영식의 보물은 하노이에 있는 하노이 탑의 모형이다. 하노이 탑은 왼쪽부터 A, B, C라고 부르는 세 막대와, 크기가 1부터 N까지인 N개의 원반으로 이루어져 있다. 처음에는 모든 원반이 막대 A에 놓여 있다. 같은 막대에서는 큰 원반이 작은 원반보다 아래에 있어야 하므로, 처음에는 크기 N인 원반이 가장 아래에 있고 크기 1인 원반이 가장 위에 있다. 원반은 한 번에 하나씩만 옮길 수 있다.

민식이는 영식이와 함께 하노이 탑을 옮기며 놀고 싶었다. 두 사람은 모든 원반을 A에서 C로 옮기는 일반적인 놀이를 이미 많이 했기 때문에, 다솜이는 새로운 규칙을 제안했다. 먼저 다솜이가 규칙에 따라 도달할 수 있는 적절한 상태를 보여준다. 처음 상태에서 그 상태로 가는 최소 이동 경로를 생각할 때, 정확히 M번 이동한 뒤의 하노이 탑 상태를 출력하는 프로그램을 작성하시오.

첫째 줄에 원반의 개수 N과 수행해야 하는 이동 횟수 M이 주어진다. 둘째 줄에는 다솜이가 보여준 목표 상태가 문자열로 주어진다. 모든 문자는 A, B, C 중 하나이다. 문자열의 첫 번째 문자는 1번 원반이 있는 막대를, 두 번째 문자는 2번 원반이 있는 막대를 나타내며, 일반적으로 i번째 문자는 i+1번 원반이 있는 막대를 나타낸다.

N은 30 이하의 자연수이다. M은 0 <= M <= m을 만족하는 정수이며, m은 처음 상태에서 입력으로 주어진 상태에 도달하는 데 필요한 최소 이동 횟수이다.

입력의 상태 문자열과 같은 형식으로 하노이 탑의 상태를 한 줄에 출력한다.

N=3이고 목표 상태가 CCC라면, AAA에서 CCC로 가는 최소 이동 경로는 AAA -> CAA -> CBA -> BBA -> BBC -> ABC -> ACC -> CCC 이다.