Cut!

Interview

Time limit2sMemory limit1024 MB

Summary

Split an n by m grid into connected pieces of exactly k cells each, printing each cell's piece number, or -1 if impossible.

Level: Easy3 of 10
Topics: Implementation, Matrix, Greedy
Solved: No attempts yet

Statement

Holding a sheet of graph paper, some of us want to cut it. In this problem you get to act on that urge.

We have only a few requests. First, the sheet may only be cut along the grid lines. Second, each resulting piece of paper must consist of exactly $k$ cells of the original sheet.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 100$ ), the height and width of the sheet in cells. The second line contains an integer $k$ ( $1 \le k \le 1000$ ).

Output

If the sheet cannot be cut in the required way, print -1. Otherwise, print $n$ lines with $m$ integers each. For each cell, print the number of the piece that contains it. Number the pieces with consecutive positive integers starting from 1.

Examples4

Example 1
Input
```
2 2
1
```
Expected output
```
1 2
4 3
```
Example 2
Input
```
2 2
2
```
Expected output
```
1 1
2 2
```
Example 3
Input
```
2 2
3
```
Expected output
```
-1
```
Example 4
Input
```
4 4
4
```
Expected output
```
1 1 1 4
1 4 4 4
2 2 3 3
2 2 3 3
```