Towers of Hanoi P93796

[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.