Дистанционный практикум по программированию

Each programmer knows the puzzle “The Hanoi Tower”. We will briefly remind you the conditions of this task.

There are 3 pivots: A, B, C. Initially, n disks of different diameter are placed on the pivot A: the smallest disk is placed on the top and every next one is placed in an increasing order of their diameters. The second and the third pivots are still empty.

You have to move all the disks from pivot A to pivot B, using pivot C as an auxiliary.

By one step you can take off 1 upper disk and put it either on an empty pivot or on another pivot over a disk with a bigger diameter.

Almost all books on programming contain a recursive solution of this task. In the following example you can see the procedure, written in Pascal.

Here, for example, the combination «BÑA» indicate that the smallest disk is on pivot B, the medium one is on pivot Ñ, the biggest one is on pivot A.

The members of jury, in preparation for the championship, played this exciting game, from time to time making notes of current ​​combinations (each on a separate sheet of paper). However, later, the sheets with recorded combinations were mixed.

Write a program that establishes if the given combination is occurred during the game.

Input

The first line of an input file contains two integer n – the number of disks, and m – the number of combinations. The following m lines contain m combinations. Each combination contains n capital letters (“A”, “B” or “C”) – the disposition of the n disks between the pivots. The first (leftmost) letter designates position (a pivot name) of the smallest disk, the second letter – position of the second largest, and so on…

Output

The output file must contain m lines – m combinations sorted in order of their appearing in game.

Limitations

1 <= n <= 250; 1 <= m <= 1000

Example

Input	Output
3 4 ACB ÂÑÀ ABB BAA	BAA ÂÑÀ ACB ABB

 

Input	Output
3 1 BCA	BCA