Color matrix

Input

The first line contains three integers $n$, $m$, $k$ (1 \leq n, m, k \leq 100, k < \min(n, m)) — representing the number of rows, columns, and the specified Manhattan distance.

Output

On the first line, output the minimum number of colors $t$ required.

For each of the following $n$ lines, output $m$ numbers — representing the color numbers assigned to each cell in the table (0 \leq c_{i,j} \leq t-1).

If multiple valid colorings exist, any one of them can be provided.

Examples

Note

In the first example, positions $(1,1)$ and $(2,2)$ are both colored with $0$, while positions $(1,2)$ and $(2,1)$ are colored with $1$. The Manhattan distance between positions $(1,1)$ and $(1,2)$ is |1-1|+|1-2|=1. Since k=1, these two positions must have different colors. However, the distance between positions $(1,2)$ and $(2,1)$ is |1-2|+|2-1|=2, allowing them to share the same color.

Scoring

1. ($17$ points): k=1;

2. ($18$ points): k=2;

3. ($14$ points): k=3;

4. ($13$ points): k=4;

5. ($24$ points): $k$ is odd;

6. ($14$ points): no additional constraints.