Color matrix

Given a field of size $n\times m$, consisting of $n$ rows and $m$ columns.

Kozak Vus wants to color the cells using the minimum number of colors. However, he wants to ensure that no two cells of the same color are exactly $k$ units apart in terms of Manhattan distance.

Recall that the Manhattan distance between two cells $(x_1,y_1)$ and $(x_2,y_2)$ is calculated as $|x_1-x_2|+|y_1-y_2|$.

Determine the minimum number of colors needed to achieve this, and provide the colored field as output.

Input

The first line contains three integers $n$, $m$, $k$ ($1\le n,m,k\le 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\le c_{i,j}\le 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.