In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]

[AED066] Magic Squares

(this problem is an adaptation from an IOI'1996 problem)

Following the success of the magic cube, Mr. Rubik invented its "planar" version, called magic squares. This is a board composed of 8 equal-sized squares, each one with a different color:

In this problem we identify each colour by an integer between 1 and 8. A board configuration is given by the colours starting in the top left corner and continuing clockwise. For example, the initial configuration (in the figure above) is given by the sequence (1,2,3,4,5,6,7,8).

There are three basic transformations that we can apply to a board, identified by the letters ‘A’, ‘B’ and ‘C’:

• A: swap the top row with the bottom row
• B: make a circular shift from one column to the right
• C: rotate the four centre squares clockwise

The following figure illustrates the state of the board after each of the three transformations has been applied to the initial board:

Using only these 3 types of transformations, any position is attainable in a maximum of 22 moves (where one move corresponds to a basic transformation).

The Problem

Given any target configuration, your task is to calculate the smallest number of moves that transforms the initial configuration into that target configuration. In addition, you must indicate the sequence of moves to be made in order to make this transformation.

Input

The input consists of a line containing 8 space separated integers, with a description of the target configuration.

Output

The first line should contain a single integer indicating the smallest number of movements to transform the initial configuration into the target configuration.

The second line should contain a set of contiguous letters identifying the minimum sequence of movements (basic transformations) calculated. If there are several minimum sequences, indicate the lexicographically smaller one.

4 8 1 3 6 2 7 5

2
BC

Explanation of Example Input 1

2 basic transformations are enough: B, followed by C

8 3 2 5 4 7 6 1

3
ACC

Explanation of Example Input 2

3 basic transformations are enough: A, followed by C, followed by C.