Description

Original source: USACO 3.2.5

After inventing the globally popular Rubik's Cube, Mr. Rubik created its two-dimensional version—the Magic Board. This is a board with $8$ squares of equal size:

1 2 3 4
8 7 6 5

We know that each square on the Magic Board has a color. These $8$ colors are represented by the first $8$ positive integers. A color sequence can be used to represent a state of the Magic Board, where the integers are taken starting from the top-left corner and moving clockwise. For the Magic Board state shown above, we use the sequence $1,2,3,4,5,6,7,8$ to represent it. This is the basic state.

Three basic operations are provided here, represented by the uppercase letters A, B, and C (these operations can be used to change the state of the Magic Board):

• A: Swap the top and bottom rows;
• B: Insert the rightmost column into the leftmost side;
• C: Rotate the central squares clockwise.

Below are demonstrations of applying these operations to the basic state:

A:

8 7 6 5
1 2 3 4

B:

4 1 2 3
5 8 7 6

C:

1 7 2 4
8 6 3 5

For each possible state, these three basic operations can be applied.

Your task is to programmatically compute the minimal sequence of basic operations required to transform the basic state into a special target state and output the sequence of operations.

Input Format

The input consists of a single line containing $8$ integers, separated by spaces, representing the target state.

Output Format

The first line of the output file should contain an integer representing the length of the shortest operation sequence. The second line should contain the lexicographically earliest operation sequence.

Sample 1

2 6 8 4 5 7 3 1

7
BCABCCB

Data Range and Hint

All numbers in the input data are integers between $1$ and $8$.