Cho 3 cọc A, B và C và n chiếc đĩa có kích thước khác nhau. Ban đầu, các chiếc đinh được đặt ở cọc A theo thứ tự lớn nhất ở dưới cùng, nhỏ dần khi đến chiếc đĩa cuối cùng.

Mục tiêu của bài toán là di chuyển toàn bộ chiếc đĩa từ cọc A sang cọc C, sử dụng cọc B làm trung gian, tuân thủ các quy tắc sau:

Chỉ có 3 cọc để di chuyển, không được thêm cọc thứ 4 nào khác.

Một lần chỉ được di chuyển một đĩa và chỉ được di chuyển chiếc đĩa nằm trên đỉnh của cọc, không được di chuyển đĩa nằm giữa.

Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn, tuy nhiên không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất.

Hãy nhập vào số lượng chiếc đĩa là N, in ra các bước di chuyển N chiếc đĩa từ cọc A sang cọc C như output mẫu bên dưới.

Ràng buộc: ~0 < N \leq 10~

Input 01:

1

Output 01:

1 -> A -> C

Giải thích: Di chuyển đĩa 1 từ A sang C

Input 02:

2

Output 02:

1 -> A -> B
2 -> A -> C
1 -> B -> C

Input 03:

3

Output 03:

1 -> A -> C
2 -> A -> B
1 -> C -> B
3 -> A -> C
1 -> B -> A
2 -> B -> C
1 -> A -> C