A Puzzling Problem

Write a program that takes from 1 to 5 puzzle pieces and, if possible, arranges them to form a 4-by-4 square.

The pieces may not be rotated or flipped: each piece keeps its original orientation. Every piece must be used, and together the pieces must cover the 4×4 square exactly, with no gaps and no overlaps. A set of pieces may have more than one arrangement that works, exactly one, or none at all.

The input describes several puzzles (sets of puzzle pieces).

The first line of each puzzle contains the number of pieces in that puzzle. Each piece is then given by a line with two integers, the number of rows and the number of columns of the piece, followed by that many lines describing the piece's shape. A shape line consists of 0 and 1 characters: a 1 marks a solid cell of the piece, and a 0 is only a placeholder. For example, a piece written as

2 3
111
101

is 2 rows by 3 columns and has its solid cells forming that shape.

Pieces are numbered in the order they appear: the first piece in a puzzle is piece #1, the next is piece #2, and so on. Every piece is valid and is no larger than 4 rows by 4 columns.

After the last piece of one puzzle, the next line gives the number of pieces in the following puzzle, and so on. A value of 0 in place of a piece count marks the end of the input.

For each puzzle, build a 4-row by 4-column square. Replace the solid cells of piece #1 with the character 1, the solid cells of piece #2 with 2, and so on, then print the four resulting rows.

If more than one valid square can be formed, output the lexicographically smallest one: read the grid as the 16-character string obtained by concatenating the four rows from top to bottom, each row from left to right, and choose the arrangement whose string is smallest.

If no valid square can be formed, print No solution possible instead. Separate the outputs of consecutive puzzles with a single blank line.