Magic Squares

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Following the success of the magic cube, rayafjyblue invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:
 
1 2 3 4   
8 7 6 5 

In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 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.
Below is a demonstration of applying the transformations to the initial squares given above:
 
A: 8765    B: 4123   C: 1724
    1234        5876        8635


All possible configurations are available using the three basic transformations.
You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.

Input

In each case, the first line contains a integer which means the case number. Next, a single line with eight space-separated integers (a permutation of (1..8)) tha t are the target configuration.

Output

Print a single integer that is the length of the shortest transformation sequence in the first line. Then, print the lexically earliest string of transformations expressed as a string of characters, 60 per line except possibly the last line.

Sample Input

1
2 6 8 4 5 7 3 1

Sample Output

7
BCABCCB

Hint

方老师想提醒她亲爱的学弟们:
这题最恶心的地方就是状态的标记了,很容易爆内存,开个7维数组水吧水吧~~当然如果你并非偶这么菜的话,可以尝试康托展开~~

Source

rayafjyblue

提交代码