하노삼의 탑

COSE214 알고리즘 강의를 수강하는 이세정 군은 최근 강의에서 '하노이의 탑' 문제를 해결하는 방법을 배웠다. 하노이의 탑 규칙은 다음과 같다.

• 기둥은 3개이며 왼쪽부터 차례로 1, 2, 3번 기둥이다.
• N개의 서로 다른 크기의 원판이 쌓여 있으며, 작은 원판 위에 큰 원판이 올라갈 수 없다.
• 각 원판에는 1번부터 N번까지 번호가 있으며, 번호가 클수록 원판이 크다.
• 한 번에 원판 하나만 옮길 수 있으며, 한 번 옮기는 데 1초가 걸린다.
• 1번 기둥에서 3번 기둥으로 모든 원판을 최소 횟수로 옮겨야 한다.
• <1> 원판은 어느 기둥에서 어느 기둥으로든 자유롭게 옮길 수 있다.

그런데 옆에 앉아 있던 삼세정 군이 자기만의 규칙을 만들고 싶다며, <1> 대신 다음 조건을 적용하면 어떻게 되는지 궁금해 했다.

• <2> 원판을 인접한 기둥으로만 옮길 수 있다. (1번 ↔ 2번 ↔ 3번)

반대쪽에 있던 사세정 군은 다음 규칙을 제안했다.

• <3> 원판을 오른쪽 기둥으로만 옮길 수 있다. 단, 3번에서는 1번으로 옮긴다. (1번 → 2번 → 3번 → 1번)

그들은 신난다며 이 문제를 '하노삼의 탑'이라고 이름 붙였다. 이세정 군은 솔직히 이런 추가 조건들이 마음에 들지 않았지만, 그래도 인싸가 되기 위해 K초 후에 각 원판이 어디에 있는지 구해보기로 했다. 그를 도와주자.

첫째 줄에 세 정수 M, N, K 가 공백으로 구분되어 주어진다.

M은 하노삼의 탑에 적용할 규칙의 번호다. 1 ≤ M ≤ 3이며, 1이면 원래 문제, 2면 삼세정 군의 규칙, 3이면 사세정 군의 규칙을 적용한다.

N과 K의 범위는 M의 값에 따라 달라진다. 자세한 범위는 다음과 같다.

• M = 1인 경우: 1 ≤ N ≤ 60, 0 ≤ K ≤ 2N-1
• M = 2인 경우: 1 ≤ N ≤ 40, 0 ≤ K ≤ 3N-1
• M = 3인 경우: 1 ≤ N ≤ 30, 0 ≤ K ≤ $\frac{3+2\sqrt{3}}{6}(1+\sqrt{3})^N+\frac{3-2\sqrt{3}}{6}(1-\sqrt{3})^N-1$

첫 번째 줄에 N개의 정수 a1, a2, ..., aN 을 공백으로 구분하여 출력한다. ai 는 K 초 후 i번 원판이 위치한 기둥의 번호이다.