Trapezoid puzzle

Draw $2n-1$ equidistant parallel lines between each of the three pairs of opposite sides of a regular hexagon. The lines divide the hexagon into equilateral triangles, and the result is a hexagonal puzzle of size $n$. Some of the triangles in the puzzle are shaded and need to be covered with puzzle pieces. Each piece is a trapezoid made of three equilateral triangles placed side by side. The pieces come in 6 colours, numbered 1 to 6, and an unlimited number of pieces of each colour is available.

Figure 1: The puzzle of size 3 from the first sample and one way to cover it.

The pieces must be placed on the hexagon so that all of the following hold:

1. Each piece fully covers three shaded triangles.
2. Each shaded triangle is covered by exactly one piece.
3. Two pieces of the same colour do not touch along the side of a triangle (they may touch at a corner).

Determine whether the puzzle can be solved, and if it can, find the solution defined in the output section.

The first line contains a positive integer $n$, the size of the puzzle ($1 \le n \le 5$).

The next $2n$ lines describe the rows of the puzzle from top to bottom. Each line is a string that describes the triangles of one row from left to right. The digit 0 is a shaded triangle and . (dot) is a triangle that is not shaded. From the top, the rows have lengths $2n+1, 2n+3, \ldots, 4n-1, 4n-1, \ldots, 2n+3, 2n+1$. Along a row, the triangles alternate in direction. In the upper $n$ rows the first triangle points up, and in the lower $n$ rows the first triangle points down.

At least one triangle is shaded.

If the puzzle cannot be solved, print nemoguce (Croatian for "impossible") on the first line.

Otherwise, print $2n$ lines that describe the solution in the same format as the input. Replace the 0 of every shaded triangle with the colour of the piece that covers it, a digit from 1 to 6, and keep every . as it is.

The placement and the colours must follow these rules, so that the answer is unique. The reading order of the triangles goes through the rows from top to bottom, and through each row from left to right.

1. Scan the shaded triangles in reading order. Whenever the scan reaches a shaded triangle that is not covered yet, place a new piece whose earliest triangle in reading order is this triangle. Only pieces that still allow all remaining shaded triangles to be covered are candidates. Among the candidates, choose the one whose second triangle in reading order comes earliest, and if that is tied, the one whose third triangle comes earliest.
2. Colour the pieces in the order they were placed. Give each piece the smallest colour number that is not used by any earlier piece sharing a triangle side with it. A piece touches at most 5 other pieces along sides, so such a colour always exists.

The covering in Figure 1 is only one valid covering and can differ from the answer these rules define.