Tower of Hanoi

Mediumjavapythonccppjavascript

Solve the Tower of Hanoi for N disks using three rods named A, B and C. Move all disks from rod A to rod C, never placing a larger disk on a smaller one.

Input Format

A single line containing the integer N.

Output Format

Print the sequence of moves, one per line, each as X -> Y meaning "move the top disk from rod X to rod Y".

Example 1

Input

Output

A -> B
A -> C
B -> C

Explanation: Two disks require three moves.

Input (stdin)

Output

Run your code to see output here...