Minimize Border Edges in Grid Coloring

Snakes is playing a game. He has an \(n \times m\) grid and \(c\) different colors (represented by integers \(1,2,\dots,c\)). He wishes to color every cell of the grid so that:

• Every cell is colored by exactly one color.
• For each color \(i\), exactly \(p_i\) cells are colored with it (with \(\sum_{i=1}^{c}p_i=n\times m\)).
• Cells that are adjacent (up, down, left, right) and share the same color are considered to be in the same connected component. Let \(q\) be the total number of edges between cells that belong to different connected components.

Your task is to construct a valid coloring of the grid that minimizes \(q\). A natural strategy is to assign cells for each color in contiguous order along a Hamiltonian path of the grid (e.g. using a snake pattern), which guarantees that all cells of the same color form a single connected component, if possible.

Note: The input guarantees that \(\sum_{i=1}^{c} p_i = n\times m\).

inputFormat

The input is given as follows:

 n m c
 p1 p2 ... pc

Where \(n\) and \(m\) are the number of rows and columns of the grid, \(c\) is the number of colors, and \(p_i\) is the number of cells that must be painted with color \(i\).

outputFormat

Output \(n\) lines. Each line contains \(m\) integers separated by spaces, representing the color of each cell in that row. The coloring must satisfy the conditions and should minimize \(q\) as explained above.

sample

2 3 2
3 3

1 1 1
2 2 2