[r]
*The Towers of Hanoi* is a game that consists of three
rods and *n* disks of different sizes that can slide onto any rod.
The game starts with all the disks stacked in order of size on
the left rod, with the biggest disk at the bottom. The aim of the game is
to move all the disks from the left rod (rod A) to the right rod
(rod C), using the middle rod (rod B) as auxiliary. The moves
have to follow these rules:

- At each step, only one disk can be moved.
- Each move consists of taking the upper disk from one rod and move it over all the disks of another rod.
- No disk can be placed over a smaller disk.

Write a program to solve the towers of Hanoi, with the minimal number of moves.

**Input**

A natural number *n* between one and ten.

**Output**

The output corresponds to the content of the three rods at each step, following the format of the example. Write a line with twenty dashes between two steps.

Public test cases

**Input**

2

**Output**

A: 2 1 B: C: -------------------- A: 2 B: 1 C: -------------------- A: B: 1 C: 2 -------------------- A: B: C: 2 1

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++