Tower of Hanoi Puzzle Solver

Solve the classical Tower of Hanoi puzzle using recursion. Given \(n\) disks and three rods, your task is to print the steps required to move all disks from the source rod to the target rod using the auxiliary rod. The puzzle follows the recurrence relation \(T(n)=2T(n-1)+1\), where the solution for \(n\) disks depends on the solution for \(n-1\) disks.

Each move should be printed in the format: Move disk X from rod S to rod T, where X is the disk number, S is the source rod, and T is the destination rod.

inputFormat

The input consists of a single line with four tokens separated by spaces:

• An integer \(n\) representing the number of disks.
• A character representing the source rod.
• A character representing the target rod.
• A character representing the auxiliary rod.

For example: 3 A C B

outputFormat

The output is the sequence of moves required to solve the Tower of Hanoi puzzle. Each move is printed on its own line in the following format:

Move disk X from rod S to rod T

Where X is the disk number, S is the source rod, and T is the target rod.

## sample

1 A C B

Move disk 1 from rod A to rod C

</p>