Puzzle Assembly

Little P collects the puzzle pieces that come in snack packages. Whenever he gathers four pieces that can be assembled into a square, he glues them onto a sheet of paper and mails them in.

The pieces are cut from cardboard and look the same on both sides, so each piece can be used in 8 different ways (in its current position, or rotated by 90°, 180°, or 270°, and the same for its mirror image).

Every piece starts as an $n \times n$ square. From each piece, two adjacent sides are chosen and some $1 \times 1$ cells are cut away: at least one cell is removed from each chosen side, and at least one cell is left on each chosen side. When the four pieces are put together they form a $(2n-1) \times (2n-1)$ square.

Each piece is labeled with a number from 1 to 4. Every cell of a piece holds that piece's number, except for the cut-out cells, which hold 0.

The four pieces above were assembled into the $7 \times 7$ square shown below.

You are given the four $n \times n$ pieces in order. Any piece may be rotated and mirrored. Assemble the four pieces into a $(2n-1) \times (2n-1)$ square so that they fit together perfectly, with no overlaps and no gaps.

The first line contains the integer $n$, the side length of a puzzle piece.

The following lines describe the four pieces in order. Each piece is given as $n$ lines, and each of those lines contains $n$ digits separated by single spaces. A blank line separates consecutive pieces.

Print $2n-1$ lines, each containing $2n-1$ digits separated by single spaces, describing the assembled square (every cell holds the number of the piece that covers it).

Several assemblies may be possible. Print the lexicographically smallest one: read every digit row by row (top to bottom, and left to right within each row) to form a single sequence, and among all valid assemblies output the sequence that is smaller at the first position where two sequences differ.

• $3 \le n \le 20$
• Every test case has at least one valid assembly.