Description

This is a magic board with $8$ squares of equal size: | $1$ | $2$ | $3$ | $4$ | |:-:|:-:|:-:|:-:| | $8$ | $7$ | $6$ | $5$ |

For the board state shown above, we use the sequence $\{1,2,3,4,5,6,7,8\}$ to represent it. This is the initial state.

There are three basic operations, denoted by the uppercase letters $\text A$, $\text B$, and $\text C$ (you can change the board state using these operations). Below is a demonstration of applying them to the initial state:

$\text A$: Swap the top and bottom rows. | $8$ | $7$ | $6$ | $5$ | |:-:|:-:|:-:|:-:| | $1$ | $2$ | $3$ | $4$ |

$\text B$: Move the rightmost column to the leftmost position. | $4$ | $1$ | $2$ | $3$ | |:-:|:-:|:-:|:-:| | $5$ | $8$ | $7$ | $6$ |

$\text C$: Rotate the four central cells clockwise. | $1$ | $7$ | $2$ | $4$ | |:-:|:-:|:-:|:-:| | $8$ | $6$ | $3$ | $5$ |

At any state during the transformation, all three basic operations can be applied.

Write a program to compute the shortest sequence of basic operations that transforms the initial state into the target state.

Input Format

A single line containing $8$ integers $a_1, a_2, \dots, a_8$ with $1 \leq a_1, a_2, \dots, a_8 \leq 8$, separated by spaces, representing the target state.

Output Format

The first line contains an integer, the length of the shortest operation sequence.

Starting from the second line, output the shortest sequence of operations as a string, wrapping every $60$ characters per line. If there are multiple solutions, output the lexicographically smallest one.

2 6 8 4 5 7 3 1 

7 
BCABCCB

Hint

Translation source: NOCOW.

Translated by ChatGPT 5