Jigsaw Puzzles

The cows are assembling alphabetical jigsaw puzzles. A puzzle has $R$ rows and $C$ columns ($1 \le R \le 10$, $1 \le C \le 10$). Instead of the usual interlocking cardboard tabs, every edge of a piece carries a letter.

Each piece is described by a serial number and its four edges. An edge is either a lowercase letter (a–z) or the character 0, which marks a border — an edge that lies on the outside of the assembled rectangle. A corner piece has two border edges, an edge piece has one, and (for a large enough puzzle) an interior piece has none.

To solve the puzzle you place every piece into the $R \times C$ grid so that:

• whenever two pieces are side by side, their touching edges show the same letter;
• every edge on the outer boundary of the grid is a border (0), and no interior edge is a border.

A piece may be rotated into any of its four orientations, but it may not be flipped over. Because the four edges are listed clockwise, rotating a piece is a cyclic shift of that list.

The figure below shows six pieces assembled one way; each touching pair of edges shares a letter, and the outside of the rectangle is all border.

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

Puzzles with larger $R$ and $C$ tend to use a more varied set of edge letters, which makes them easier to assemble. A valid assembly always exists.

• The first line contains two integers $R$ and $C$.
• Each of the next $R \times C$ lines describes one piece: an integer serial number followed by its four edge identifiers, listed clockwise.

Print the assembled puzzle as $R \times C$ lines. The line numbered $C \cdot (i-1) + j$ describes the piece placed at row $i$, column $j$ (rows and columns are 1-indexed, row by row): print its serial number followed by its four edges in the order top, right, bottom, left.

More than one assembly may satisfy the rules. Print the lexicographically smallest one, defined as follows. Read each assembly as the sequence of its lines in the order above, where a line is the tuple

$$(\text{serial}, \text{top}, \text{right}, \text{bottom}, \text{left}).$$

Compare two assemblies by comparing these tuple sequences element by element: serial numbers compare as integers and edge characters compare by their character value. Output the single smallest assembly under this order.