MAGIC SQUARES

Program

MAGIC.PAS, MAGIC.C, MAGIC.CPP)

Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares (see Figure 1).

---------
|1|2|3|4|
|8|7|6|5|
---------

Figure 1: Initial configuration

In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 1). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 1 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration. Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet:

'A': exchange the top and bottom row,
'B': single right circular shifting of the rectangle,
'C': single clockwise rotation of the middle four squares.
All configurations are available using the three basic transformations.
----------------------------------------------------------------------

  A:   1 2 3 4
    ---------
    |8|7|6|5|
    |1|2|3|4|
    ---------
     8 7 6 5

B:   1 2 3 4
    ---------
    |4|1|2|3|
    |5|8|7|6|
    ---------
     8 7 6 5

C:   1 2 3 4
    ---------
    |1|7|2|4|
    |8|6|3|5|
    ---------
     8 7 6 5

Figure 2: Basic transformations
----------------------------------------------------------------------
The effects of the basic transformations are described in Figure 2. Numbers outside the squares denote square positions. If a square in position p contains number i, it means that after applying the transformation, the square whose position was i before the transformation moves to position p.

You have to write a program that computes one of possible sequences of basic transformations that transforms the initial configuration of Figure 1 to a specific target configuration.

Input Data

The file MAGIC.IN contains rows of 8 positive integers, the descriptions of the target configuration. End of data is given by end of file.

Output Data

For each given target configuration the output in MAGIC.OUT consists of the folowing block of lines:
In the first line there is the length L of the transformation sequence. On the following L lines there is the sequence of identifiers of basic transformations, one letter in the first position of each line. There is no blank lines between blocks.

Example Input and Output
--------------------------------------------------------------
MAGIC.IN                MAGIC.OUT
6 4 2 8 1 3 5 7         7
8 7 6 5 4 3 2 1         A
                        C
                        A
                        B
                        C
                        C
                        B
                        1
                        A