Towers of Hanoi

Video preview
A video by Reducible - Towers of Hanoi: A Complete Recursive Visualization
 
Given 3 rods (left - 1, middle - 2, and right - 3), there are n round disks on the first rod or different sizes. The disks are placed in increasing order of size from top to bottom. You are allowed to move the top disk from one rod to another and place it on top of another larger disk. So, you’re not allowed to place a larger disk on top of a smaller one.
You are asked to print all the operations that would lead to moving all the disks from the first rod to the third one. The number of moves needs to be minimal.

Input

The input contains a single integer n (1 ≤ n ≤ 16) the number of disks on the first rod.

Output

The program should print all the operations required to move the disks from the first rod to the third one while making sure that all the disks on a rod are smaller than the ones below. The output should not contain more than operations.

Examples

Input
Output
2
1 -> 2 1 -> 3 2 -> 3
3
1 -> 3 1 -> 2 3 -> 2 1 -> 3 2 -> 1 2 -> 3 1 -> 3
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue