Disjoint 2x2 Flower Cycles

We are given an (N)-by-(M) grid, where each cell must be planted with a flower. There are (K) types of flowers numbered from 1 to (K). A valid arrangement must satisfy the following conditions:

1. Each flower type appears in at least one cell.
2. For every flower type, the cells with that type form a single 4-connected component. (Two cells are 4-adjacent if they share a side.)
3. For every cell ((i,j)), exactly two of its 4-adjacent neighbors have the same flower type as the flower planted in ((i,j)).

A natural way to satisfy the third condition is to have each group of cells of the same flower type form a cycle (i.e. a closed ring) such that every cell in that cycle is adjacent (in the grid) exactly to its two neighbors in the cycle. In a grid, the smallest possible cycle has length 4 and a canonical example is a 2x2 block with the cycle order (top-left, top-right, bottom-right, bottom-left). In such a block each cell has exactly two adjacent cells in the cycle and no extra adjacent cell from the same block (note that cells in different cycles must have different flower types).

In this problem, you need to output a valid configuration (an assignment of flower types to grid cells) or output -1 if it is impossible. In our construction we will only produce a solution in the following case:

• The grid dimensions satisfy both \(N\) and \(M\) are even (so that the grid can be partitioned into disjoint 2x2 blocks),
• and the number of flower types exactly equals the number of 2x2 blocks, i.e. \(K = \frac{N\times M}{4}\),
• and clearly \(N\times M\) is even and \(4K \le N\times M\) holds.

If these conditions hold, one valid solution is to partition the grid into 2x2 subgrids and assign each block a distinct flower type. In each 2x2 block, label the cells as follows:

[ \begin{array}{cc} A & B\ D & C \end{array} ]

with a cycle order (A \to B \to C \to D \to A). Then cell A is adjacent to B and D, cell B is adjacent to A and C, etc. This satisfies the condition that each cell has exactly two 4-adjacent neighbors with the same flower type and cells from different cycles (blocks) have different flower types.

Otherwise, output -1.

Note: For this problem, if the input does not meet the above conditions, you should output -1. For example, if either (N) or (M) is odd or (K \ne \frac{N\times M}{4}), the answer is -1.

inputFormat

The input consists of a single line containing three integers (N), (M) and (K) ( (1 \le N,M \le 500,\ 1 \le K \le N\times M)).

It is guaranteed that if a valid construction exists then the following necessary conditions hold:

• (N) and (M) are even (so that the grid can be partitioned into 2x2 blocks),
• (K = \frac{N\times M}{4}).

Otherwise, a valid configuration is impossible.

outputFormat

If a valid configuration exists, output (N) lines, each containing (M) integers separated by spaces. The (j)-th integer in the (i)-th line represents the flower type (an integer between 1 and (K)) assigned to cell ((i,j)). It is guaranteed that using the printed assignment, every cell in the grid has exactly two 4-adjacent neighbors with the same type, and for each flower type, the cells of that type form a 4-connected cycle (a 2x2 block cycle).

If no valid configuration exists under the above restrictions, output a single line with -1.

sample

2 2 1

1 1
1 1

</p>