题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day2 T1. Кольорова матриця

给定一个 $n \times m$ 的网格，即包含 $n$ 行和 $m$ 列。

科扎克·武斯希望用最少的颜色对网格中的单元格进行着色，但要求不存在两单元格具有相同颜色且它们之间的曼哈顿距离等于 $k$。

提醒一下，两个单元格 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

请找出所需的最少颜色数量，并输出一个符合要求的着色方案。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n, m, k \leq 100, k < \min(n, m))$，分别表示网格的行数、列数以及固定的曼哈顿距离。

输出格式

第一行输出一个整数 $t$，表示所需的最少颜色数量。

接下来的 $n$ 行，每行包含 $m$ 个整数，表示对应单元格的颜色编号 $(0 \leq c_{i,j} \leq t-1)$。

如果存在多种可能的着色方案，可以输出任意一种。

2 2 1

2
0 1
1 0

在第一个样例中，位置 $(1,1)$ 和 $(2,2)$ 着色为 $0$，位置 $(1,2)$ 和 $(2,1)$ 着色为 $1$。位置 $(1,1)$ 和 $(1,2)$ 之间的曼哈顿距离为 $|1-1| + |1-2| = 1$，由于 $k=1$，这两个位置必须使用不同的颜色。而位置 $(1,2)$ 和 $(2,1)$ 之间的曼哈顿距离为 $|1-2| + |2-1| = 2$，因此它们可以具有相同的颜色。

4 4 2

4
0 2 3 1
0 1 3 2
3 1 0 2
3 2 0 1

数据范围与提示

详细子任务附加限制及分值如下表所示：