Paper Cutting

Song Yujin has an L x L square sheet of grid paper. The sheet has L cells across and L cells down, and each cell is a 1 x 1 square.

Cha Younghoon cut the sheet along grid lines into exactly 5 pieces. Yujin must now place the five given pieces back into an L x L square without rotating any piece.

The first line contains the side length L of the square. (3 <= L <= 10)

Then the descriptions of the first through fifth pieces are given in order.

Each piece is described in the following format.

• The first line contains the piece height N and width M. (1 <= N, M <= L)
• The next N lines describe the shape of the piece. Each line has length M and consists only of # and ..
• # means a cell occupied by the piece, and . means an empty cell.
• In the given bounding rectangle, the first row, last row, first column, and last column each contain at least one #.

If the five pieces can be placed without rotation inside the L x L square so that they do not overlap and every cell is filled, print the piece number occupying each cell. Pieces are numbered 1 through 5 in input order.

Print L lines, each containing the L numbers in that row.

If there are multiple valid arrangements, concatenate all rows from top to bottom and print the arrangement whose resulting string is lexicographically smallest.

If no valid arrangement exists, print gg.