Description

Given the grayscale values of every pixel in a $3 \times 3$ image and a target image, find the shortest and, among those, lexicographically smallest non-empty sequence of operations.

The possible operations and their corresponding characters are: A: rotate $90$ degrees clockwise; B: rotate $90$ degrees counterclockwise; C: flip left–right; D: flip up–down.

Input Format

• Three lines, each containing $3$ integers, representing the initial image matrix.
• Three lines, each containing $3$ integers, representing the target image matrix.

Output Format

Output the shortest, lexicographically smallest non-empty operation sequence. If there is no solution, or if the shortest sequence would have length greater than $10^8$, output Poland cannot into space!!!.

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

D

Hint

The string length does not exceed $10^8$.

Translated by ChatGPT 5