Jigsaw Puzzle Assembly

Little Z loves jigsaw puzzles but struggles to assemble them. He is given several puzzle pieces that together form a complete \(4\times4\) square. Each piece is represented as a grid of characters where 1 indicates a filled cell and 0 an empty cell. Note that the pieces cannot be rotated or flipped – they may only be translated.

Your task is to determine a valid placement for all pieces so that they exactly cover the board without overlapping. If a valid tiling exists, output the board configuration with each cell labeled by the piece number (starting from 1). If no solution exists, output -1.

Rules:

• The board is of size \(4\times4\).
• Each piece must lie entirely within the board.
• Pieces do not overlap.
• The union of all piece cells must cover the board exactly.

inputFormat

The first line contains an integer n (which will be 4).

For each of the n pieces, the first line contains two integers r and c indicating the number of rows and columns in the piece's grid. This is followed by r lines each containing a string of c characters (each being either 1 or 0). The filled cells (with 1) indicate the shape of the piece.

outputFormat

If a valid tiling exists, output 4 lines, each with 4 space-separated integers. The integer in a cell indicates the piece number occupying that cell. If multiple solutions exist, output any one of them. If no valid arrangement exists, output -1.

sample

4
2 2
11
11
2 2
11
11
2 2
11
11
2 2
11
11

1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4