문제

세 개의 장대와 반경이 서로 다른 개의 원판이 있다. 번째 () 원판은 번째 원판보다 반경이 작다.

번째 () 원판은 번째 장대에 놓여져 있으며, 각 장대에는 원판이 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 모든 원판을 세 번째 장대로 옮기려 한다.

• 한 번에 한 개의 원판만을 다른 장대로 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

이동 횟수의 최솟값이 이하인 입력만 주어진다.

입력

첫째 줄에 정수 이 주어진다.

둘째 줄에 이 공백으로 구분되어 주어진다.

출력

첫째 줄에 작업을 수행하는데 필요한 최소 이동 횟수 를 출력한다.

다음 개의 줄의 번째 () 줄에는 를 (; ) 공백으로 구분하여 출력한다.

이는 번째 원판을 번째 장대로 옮겼음을 의미한다.

제약 조건

• ()
• 입력으로 주어지는 모든 수는 정수이다.