Snake Cube

A snake cube is a puzzle made of 27 wooden unit cubes threaded onto a single rubber band. The band passes through the center of every cube, entering through the center of one face and leaving through the center of another. On the first cube the band simply starts at the center (there is no incoming band), and on the last cube it ends at the center (there is no outgoing band). Two neighbouring cubes can be freely rotated about the center of the face they share. Because the cubes are held together only by the rubber band, the puzzle can be stretched out flat while you solve it, so it can take shapes that a rigidly strung version could not.

The 27 cubes are painted in two alternating colours, written as uppercase and lowercase letters. Following the band from the start, the first cube is A, the second a, the third B, the fourth b, and so on; the 27th (last) cube is N. In other words the order is A, a, B, b, C, c, ..., M, m, N.

Given a snake cube laid out flat on a plane, write a program that determines its shape after it is folded into a 3×3×3 cube.

The first 15 lines each contain 15 characters and describe the puzzle laid out flat. An empty cell is .. The 14 uppercase letters A through N and the 13 lowercase letters a through m are placed on the grid, and the rubber band links them in the order A, a, B, b, ..., N.

The given layout is always valid, meaning it satisfies all of the following:

• Each of the 27 letters appears exactly once.
• Two cubes that are neighbours in the order are also orthogonally adjacent on the grid.
• Neighbouring cubes are joined by the rubber band through the faces they share.

The given puzzle can always be folded into a 3×3×3 cube.

Print three lines. Each line describes one layer (a 3×3 face) of the folded 3×3×3 cube: the first line is the first layer, the second line the second layer, and the third line the third layer. A line consists of three groups separated by single spaces, and each group is one row of that layer (three cubes). Each line therefore contains 9 letters and 2 spaces, 11 characters in total.

A snake cube can be folded in several orientations that differ by rotation and reflection. Among all valid foldings, print the one whose entire output text is lexicographically smallest.

Whether a cube is a straight piece (the band runs through two opposite faces) or a corner piece (the band runs through two adjacent faces) is an intrinsic property of the puzzle; you can read it off the flat layout by checking, for every three consecutive cubes, whether they are collinear or make a turn. This straight/corner structure is preserved after folding.