Image Transformation Sequence

You are given two 3×3 images. The first image is the initial image and the second is the target image. Each image is represented by 3 lines containing 3 integers (grayscale values) each. You are also given four operations which can transform an image as follows:

• A: Rotate the image clockwise by $90^\circ$.
• B: Rotate the image counterclockwise by $90^\circ$.
• C: Flip the image horizontally (left to right).
• D: Flip the image vertically (upside down).

Your task is to determine the shortest sequence of operations which transforms the initial image into the target image. In case there are multiple sequences of the shortest length, output the lexicographically smallest sequence (comparing the operation characters in the order A < B < C < D). If no operations are needed, output an empty string.

All transformations use the standard definitions (using $\LaTeX$ for formulas, e.g. a $90^\circ$ clockwise rotation means that the pixel located at position $(i,j)$ in the original image moves to $(j,3-i+1)$ in the new image). You may assume that a solution always exists.

inputFormat

The input consists of 6 lines. The first 3 lines describe the initial image, each line containing 3 integers separated by spaces. The next 3 lines describe the target image in the same format.

For example:

1 2 3
4 5 6
7 8 9
7 4 1
8 5 2
9 6 3

outputFormat

Output the shortest lexicographically smallest sequence of operations (a string consisting of characters A, B, C, D) that transform the initial image to the target image. Output an empty string if no transformation is needed.

sample

1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9