Reassemble the Puzzle

Fili and Floi are playing a jigsaw puzzle game. Fili cuts an original rectangular paper into k = n^2 pieces according to a set of well‐formed rules. The original paper is a W × H grid of cells with W = w \cdot n and H = h \cdot n (where w and h are known, but n is not revealed to Floi). In a trivial dissection the paper would be divided into n^2 rectangles each of size w × h cells. However, to create a proper jigsaw puzzle the pieces are cut along the grid lines so that:

• Each piece is a simple 4-connected region without holes.
• Every cell of the original paper belongs to exactly one piece.
• Each piece must contain the four corners of its corresponding w × h rectangle (from the trivial puzzle).
• The cells in each piece may come only from the corresponding w × h rectangle, the cells adjacent to it, and the interior of the immediately adjacent rectangles.
• The cut between two adjacent pieces is not a straight line (except for pieces on the border of the paper).

A consequence of these constraints is that every piece will fit within a grid of size (3w-2) × (3h-2) in such a way that the central w × h block is exactly the corresponding trivial rectangle. Fili shuffles the pieces (without rotating them) and Floi’s task is to reassemble the original paper.

You are given the descriptions of all pieces. The i-th piece is described by a grid of characters of size (3w-2) rows and (3h-2) columns. In each such grid, a cell marked with an 'X' indicates that the cell is part of the piece, and a '.' indicates it is not. When reassembling the puzzle, the central w × h part of each piece must appear in the corresponding cell block of the final board. Specifically, when a piece is placed in the trivial position at row i and column j (0-indexed), its central region (starting at row h-1 and column w-1 in the piece grid) will align with the board cells from row i·h to i·h+h-1 and column j·w to j·w+w-1.

Your task is to determine an assignment of pieces to the n × n grid (without rotation) such that the union of all pieces exactly covers the board of size H = n · h rows and W = n · w columns with no overlaps and no uncovered cells. You should output the assignment as an n × n grid of piece indices (numbered from 1 to n^2) where the piece placed at the trivial position (row, column) uses its pattern shifted by a fixed offset. (Note that for this problem, all test cases will have n = 2 so that every piece lies on the border of the original paper and therefore may have straight sides.)

If there are multiple solutions, output any one.

Input formulas in LaTeX:

• Original paper size: \(W = w \cdot n\), \(H = h \cdot n\).
• Piece bounding box: \((3w-2) \times (3h-2)\).
• Number of pieces: \(k = n^2\).

inputFormat

The input begins with a line containing three integers n, w, and h (n = 2 in all test cases), where the final board has H = n · h rows and W = n · w columns.

Then, for each of the n² pieces, its description is given as (3h-2) lines, each containing exactly (3w-2) characters. Each character is either 'X' (denoting a cell that is part of the piece) or '.' (denoting an empty cell). The central w × h block of each piece (starting at row h-1 and column w-1) is guaranteed to be filled with 'X'.

outputFormat

Output n lines, each containing n integers. The j-th integer in the i-th line (1-indexed) is the index (from 1 to n²) of the piece placed at the corresponding position in the puzzle. The pieces are placed such that when each is shifted by the proper offset, the union of the pieces exactly covers the board without overlapping.

sample

2 2 2
....
.XX.
.XX.
....
....
.XX.
.XX.
....
....
.XX.
.XX.
....
....
.XX.
.XX.
....

1 2
3 4