Description

$\text{Snakes}$ is playing a game where he colors squares on a white paper with $n\times m$ grid cells. However, messy coloring is not fun, so he came up with a peculiar problem:

In an $n\times m$ grid, use $c$ different colors to try to color all cells. Different colors are represented by integers in $1...c$. The coloring must satisfy the following conditions:

• Each cell must be colored in exactly one color.

• Color $i$ must color exactly $p_i$ cells. It is guaranteed that $\sum_{i=1}^c p_i = n\times m$.

• Consider cells that are adjacent up, down, left, or right and have the same color to be in the same connected component, and define $q$ as the number of grid edges between different connected components. See the sample explanation.

Now, $\text{Snakes}$ wants to know, given $n$, $m$, $c$ and $p_1...p_c$, whether you can construct a valid coloring that makes $q$ as small as possible.

Input Format

The first line contains three numbers, $n,m,c$.

The second line contains $c$ numbers, where the $i$-th number is $p_i$.

Output Format

Output $n$ lines, each containing $m$ numbers, representing your constructed $n\times m$ coloring with $q$ as small as possible.

2 3 3
1 2 3

2 3 1
2 3 3

Hint

   |   |   
 2 | 3 | 1 
   +   +---
 2 | 3   3 
   |       

For the sample, $q=4$, consisting of three vertical edges and one horizontal edge.

Conventions

This problem is Special Judge.

For each test point, a threshold $w$ is set, and it is guaranteed that there exists a construction such that $q\leq w$.

The score for your output will be computed as follows:

$$\begin{matrix}q&score&q&score\\\\ q \leq w&10&1.75w < q \leq 2w&5\\\\ w < q \leq 1.1w&9&2w < q \leq 2.3w&4\\\\ 1.1w < q \leq 1.25w&8&2.3w < q \leq 2.6w&3\\\\ 1.25w < q \leq 1.5w&7&2.6w < q \leq 3w&2\\\\ 1.5w < q \leq 1.75w&6&3w < q \leq 3.5w&1\end{matrix}$$

If $q > 3.5w$, it will be judged as Wrong Answer.

The score shown during the contest is the final score.

Constraints

For $10\%$ of the testdata, $1\leq n,m\leq 3$, $c\leq 3$.

For $30\%$ of the testdata, $1\leq n,m\leq 8$, $c\leq 6$.

For $50\%$ of the testdata, $1\leq n,m\leq 15$, $c\leq 25$.

For $100\%$ of the testdata, $1\leq n,m\leq 20$, $c\leq 50$, $p_i\leq 20$.

Translated by ChatGPT 5