Another Puzzling Problem

Write a program that solves jigsaw puzzles. The input describes the size of the puzzle, the size of the pieces, and every piece. Each piece is drawn with ASCII characters. Your program must print the solved puzzle: all pieces assembled into their correct positions.

The first line contains three integers $N$, $H$, and $W$: the number of pieces along one side of the puzzle (a puzzle is always an $N \times N$ square), the height of a piece, and the width of a piece. Every piece has the same size. The bounds are $2 \le N \le 10$ and $1 \le H, W \le 25$. For example, 2 2 3 describes a $2 \times 2$ puzzle whose pieces are each $2$ characters tall and $3$ characters wide.

The remaining input describes the $N \times N$ pieces in arbitrary order. Each piece consists of its image — exactly $H$ lines of $W$ characters — followed by one line with four integers in the range $[-5, 5]$: the shapes of the top, left, bottom, and right edges, in that order. A value of $0$ marks a straight (outer) edge. Two edges fit together exactly when their values are opposite and sum to $0$ (for example $+5$ locks into $-5$, and $+4$ into $-4$). Pieces are never rotated, and no two pieces share the same four edge values (all pieces are distinct). A blank line separates consecutive pieces.

Spaces (ASCII code 32) are ordinary characters and may appear anywhere in a piece, including at the end of a line or as an entire line; they always appear in the input where they belong. Every piece is a solid rectangular block of characters (ASCII codes 32 to 127), so treat a space exactly like any other character.

Print the solved puzzle. There is exactly one way to lay out the $N \times N$ pieces: every outer edge (value $0$) lies on the border, the right edge of each piece and the left edge of its right-hand neighbour sum to $0$, and the bottom edge of each piece and the top edge of the piece below it sum to $0$. Print the resulting picture, which is $N \cdot H$ lines of $N \cdot W$ characters. The input always has exactly one solution.