Around the end of the 19th century, a kind of intellectual toy was sold in European shops. There were three rods on a copper plate, and a tower composed of 64 disks was strung on the leftmost rod from top to bottom, from small to large.

The goal is to move all the disks from the leftmost rod to the middle rod, under the condition that only one disk can be moved at a time, and a larger disk is not allowed to be placed on top of a smaller disk.

This is a famous problem, found in almost all textbooks.

Since only one disk can be moved at a time, and a larger disk cannot be placed on a smaller one, the number of moves required for 64 disks is: 18,446,744,073,709,551,615.

This is an astronomical number. If one move could be calculated (without output) per microsecond, it would still take almost a million years.

We can only find the solution to the problem and solve the Towers of Hanoi for smaller values of N, but it is very difficult to solve the 64-layer Towers of Hanoi using a computer.

Assume the disks are numbered from small to large as 1, 2, ...

Input Format

The input consists of an integer followed by three single-character strings. The integer is the number of disks, and the following three characters represent the labels of the three rods.

Output Format

Output the record of each move of the disks. One move per line. Each move is recorded in the form, for example, a->3->b, which means moving disk number 3 from rod a to rod b.

Data Range

The number of disks is in the range [1, 20].

Input Example:

2 a b c

Output Example:

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