설명

약 $19$세기 말, 유럽 주의 상점에서 지적 장난감을 판매했는데, 동판에 세 개의 막대가 있고, 맨 왼쪽 막대에는 위에서 아래로, 작은 것부터 큰 것까지 순서대로 $64$개의 원반으로 구성된 탑이 꽂혀 있었다.맨 왼쪽 스틱의 디스크를 모두 가운데 스틱으로 옮기는 것이 목적이다. 한 번에 한 디스크만 움직일 수 있고 큰 디스크를 작은 디스크 위에 놓을 수 없다는 조건이다.이것은 유명한 문제인데, 거의 모든 교재에 이 문제가 있다.조건은 한 번에 한 디스크만 이동할 수 있고 큰 디스크를 작은 디스크 위에 놓을 수 없기 때문에$64$한 디스크의 이동 횟수는 $18446744073709551615$천문학적인 숫자이다. 만약 1마이크로초당 한 번의 이동을 계산할 수 있다면 (출력하지 않음) 거의 $1$백만 년이 걸린다.우리는 문제의 해결 방법을 찾아내고 작은 $N$ 값일 때의 한노타만 해결할 수 있지만, 컴퓨터로 $64$층의 한노타를 해결하기는 어렵다.디스크의 작은 번호에서 큰 번호로 $1, 2,3...$

형식 입력

정수 $N(N<20)$뒤에 세 개의 단일 문자열을 입력합니다.정수는 접시의 수이고 다음 세 문자는 세 막대의 번호를 나타냅니다.

출력 형식

각 단계에서 이동한 접시의 기록을 출력합니다.한 번에 한 행씩 이동합니다.매번 이동하는 기록은 예를 들어 a->3->b의 형식이다. 즉, 번호가 3인 접시를 a봉에서 b봉으로 옮긴다.

샘플

2 a b c

a->1->c
a->2->b
c->1->b