printРабочее место участника


1890. Folding Snake Cube

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Snake Cube is a puzzle that consists of 27 wooden cubelets that are connected by an elastic band running through them. The band starts in the center of the first cubelet, exits through the center of one of its faces that is adjacent to the face of the second cubelet. Then the band enters through the center of the adjacent face into the second cubelet, exits the second cubelet through the center of some other face, enters the third cubelet and so on until the last cubelet where the band ends. This configuration allows adjacent cubelets to freely turn around the center of their shared faces. Moreover, the elasticity of the band allows to stretch it during intermediate steps and to fold the puzzle in a ways that would be otherwise impossible with rigid connections between cubelets. The task is to fold it into a `3\ times\ 3\ times\ 3` cube


Cubelets in the Snake Cube puzzle are typically colored into two alternating colors. For the purpose of this problem all cubelets are marked by alternating uppercase and lowercase letters. The first cubelet is marked by 'A', the second one by 'a', the third one by 'B', the fourth one by 'b', and so on. The last 27th cubelet is marked by 'N'. The order of marking follows the path of the band through the cubelets.


Initially the puzzle is laid out on a flat surface and its layout is given the input file. Your task is to find a way to fold it into a `3\ times\ 3\ times\ 3` cube and describe the resulting layout in the output file.
The input file consists of 15 lines with 15 characters on each line that represent flat layout of the puzzle. Dot characters ('.') represent empty space. Uppercase letters from 'A' to 'N' and lowercase letters from 'a' to 'm' represent marked cubelets with the band running through AaBb…N as explained in the problem statement.
The input file represents a valid layout. In a valid layout:
  • each marked cubelet appears exactly once;
  • cubelets that are adjacent in the order that elastic band runs through them are also adjacent in the layout;
  • a face that the band exists a cubelet from is adjacent to the face of the next cubelet that the band enters into.
The puzzle given in the input file is solvable and can be folded into a `3\ times\ 3\ times\ 3` cube.
Write to the output file 3 lines with 11 characters on each line (3 groups of 3 characters separated by single spaces) that represent the puzzle in the input file folded into a `3\ times\ 3\ times\ 3` cube. The output file corresponds to 3 consecutive `3\ times\ 3` slices of the resulting layout.
The output file layout has to be valid in the same sense as in the input file.

Sample Input


Sample Output

AhI jJi DdE
aHl KkL cFe
BgM bGm CfN
Sample input and output correspond to the layouts that are shown on the pictures in the problem statement.
Source: ACM ICPC NEERC, 2012