Description

Around the late 19th century, a puzzle toy was sold in European shops. It consisted of a copper plate with three rods, where the leftmost rod held a tower of 64 disks arranged from top to bottom in ascending order of size. The objective was to move all the disks from the leftmost rod to the middle rod, under the conditions that only one disk could be moved at a time and a larger disk could never be placed on top of a smaller one.

This is a famous problem that appears in almost all textbooks. Given the constraints—only one disk can be moved at a time, and larger disks cannot be placed atop smaller ones—the number of moves required for 64 disks is: 18,446,744,073,709,551,615.

This is an astronomical number. Even if a move could be calculated (without output) every microsecond, it would still take nearly a million years. We can only find the solution to the problem and solve the Tower of Hanoi for smaller values of N, but solving the 64-layer Tower of Hanoi with a computer remains extremely challenging.

Assume the disks are numbered from smallest to largest as 1, 2, ...

Input Format

The input consists of an integer (less than 20) followed by three single-character strings.
The integer represents the number of disks, and the three characters denote the labels of the three rods.

Output Format

Output each step of moving the disks, one move per line.
Each move should be recorded in the format a->3->b, indicating that disk number 3 is moved from rod a to rod b.

2 a b c

a->1->c
a->2->b
c->1->b