하노이의 탑에서 한 번의 이동

고전적인 하노이의 탑 문제를 다룬다. 기둥 세 개와 반지름이 모두 다른 원판 여러 개가 있고, 원판의 개수를 $n$이라 하자. 지켜야 할 규칙은 하나뿐이다. 작은 원판 위에 큰 원판을 올릴 수 없다. 원판에는 가장 작은 것을 1번, 가장 큰 것을 $n$번으로 하여 번호를 매기고, 기둥은 A, B, C라고 부른다. 처음에 원판이 모두 기둥 A에 쌓여 있고 한 번에 한 개씩 옮겨서 기둥 C로 전부 옮기는 것이 목표라면, 잘 알려진 풀이가 있다. 위쪽 $n-1$개를 A에서 B로 재귀적으로 옮기고, 맨 아래 원판을 A에서 C로 곧바로 옮긴 다음, B에 쌓인 $n-1$개를 다시 C로 재귀적으로 옮기는 방법이다.

고전적인 하노이의 탑 문제를 푸는 재귀 의사코드는 다음과 같다.

move(num_disks, from_post, spare_post, to_post)
    if (num_disks == 0)
        return
    move(num_disks - 1, from_post, to_post, spare_post)
    print ("Move disk ", num_disks, " from ",
        from_post, " to ", to_post)
    move(num_disks - 1, spare_post, from_post, to_post)

$k$와 $n$이 주어질 때, 위 알고리즘이 출력하는 $k$번째 이동이 무엇인지 구하는 문제다.

입력은 한 줄에 정수 두 개 $k$와 $n$이 주어지는 형태다. 두 정수가 모두 0인 줄이 나오면 입력이 끝난다.

입력은 모두 유효하다. $k$와 $n$은 양의 정수이고, $k$번째 이동이 실제로 존재하도록 $k < 2^n$이며, 답이 64비트 정수 자료형에 들어가도록 $n \le 60$이다.

각 테스트 케이스마다 위 알고리즘이 만드는 $k$번째 이동을 출력한다. 형식은 다음을 정확히 따른다. Case, 공백 한 칸, 테스트 케이스 번호, 콜론과 공백 한 칸, 그다음에 그 케이스의 답을 원판 번호, 출발 기둥 이름, 도착 기둥 이름 순서로 쓰되 각 부분을 공백 한 칸으로 구분한다. 줄 끝에 공백을 남기지 않는다.