Hanoi tower#6187
Each programmer knows the puzzle "Tower of Hanoi." We will briefly remind you of the conditions of this task.
There are rods: A, B, C. Initially, disks of different diameters are placed on rod A: the smallest disk is at the top, and every next one is placed below in increasing order of their diameters. The second and third rods are empty.
You have to move all the disks from rod A to rod B, using rod C as an auxiliary.
In one move you can remove the topmost disk from a rod and place it on either an empty rod or on top of another disk of larger diameter.
Almost all programming books contain a recursive solution of this task. Below you can see the procedure, written in Pascal:
Procedure Hanoi (A, B, C: integer; N: integer);
Begin If N > 0 then Begin Hanoi (A, C, B, N-1); Writeln('Disk ', N, ' from ', A, ' to ', B); Hanoi (C, B, A, N-1); End End;
For example, the combination "BCA" means that the smallest disk is on rod B, the medium one is on rod C, and the largest one is on rod A.
During preparations for the championship, the jury members played this exciting game, occasionally noting down the current combinations (each on a separate sheet of paper). However, these sheets were later mixed together.
Write a program that determines for each given combination whether it occurred during the course of the game, and outputs all given combinations sorted in the order they appear in the standard sequence of the game.
The first line contains two integers, (1 \leq n \leq 250) — the number of disks, and (1 \leq m \leq 1000) — the number of combinations. Each of the following lines contains a combination, which is a string of uppercase letters ("A", "B", or "C") describing the positions of the disks on the rods. The first (leftmost) letter indicates the position (rod name) of the smallest disk, the second letter indicates the position of the second smallest disk, and so on.
Output lines — the combinations given in the input, sorted in the order they occur during the game.
Example 1