题目描述

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

哥萨克 Vus 希望用最少数量的颜色为单元格着色。但他要求不存在两个颜色相同的单元格，且它们之间的曼哈顿距离等于 $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

4 4 2

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

提示

说明

在第一个示例中，位置 $(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$，因此它们可以使用相同的颜色。

评分标准

• （17 分）：$k=1$；
• （18 分）：$k=2$；
• （14 分）：$k=3$；
• （13 分）：$k=4$；
• （24 分）：$k$ 为奇数；
• （14 分）：无额外限制。

翻译由 DeepSeek V3 完成