丹麦人非常嫉妒其他国家拥有好得多的滑雪斜坡。这个问题甚至被提交到了欧洲法院，法院决定重新划分欧洲国家的边界，以使滑雪斜坡的分布尽可能公平。欧洲可以被建模为一个大小为 $R \times C$ 的网格，其中第 $i$ 行第 $j$ 列的单元格包含一个数字 $m_{ij}$，表示该单元格中有多少座山。一个国家由一组连通的单元格组成，该国家内的山脉总数除以该国家的面积决定了在那里滑雪的舒适度。如果一个国家内的任意两个单元格都可以通过仅在四个基本方向（即不能沿对角线）移动而相互到达，则该国家是连通的。请帮助丹麦人将欧洲划分为 $N$ 个国家，使得山脉相对于国家面积的分布尽可能均匀！

输入格式

第一行包含一个整数 $T$，表示测试用例的编号。

第二行包含三个整数 $R$，$C$（$2 \le R \times C \le 10^5$）和 $N$（$1 \le N \le 16000$），分别表示网格的行数、列数以及国家的数量。

接下来的 $R$ 行，每行对应网格中的一行。每行包含 $C$ 个数字。在第 $i$ 行第 $j$ 列，数字 $m_{ij}$（$0 \leq m_{ij} \leq 1000$）表示网格中对应位置的山脉数量。

输出格式

这 $N$ 个国家从 $0$ 到 $N - 1$ 进行编号。输出 $R$ 行，每行包含 $C$ 个数字，其中每个数字表示在划分后拥有该单元格的国家编号。

样例

输入样例 1

0
2 2 3
1 5
4 2

输出样例 1

0 0 
1 2

说明

图 1：样例 1 中的国家划分。

在第一个样例中，$\bar{a} = \frac{1 + 5 + 2 + 4}{4} = 3$。红色国家的平均值为 3，蓝色国家的平均值为 2，绿色国家的平均值为 4。这给出 $S = 2$。

输入样例 2

0
4 6 6
1 2 2 3 5 3
5 6 7 4 5 3
5 7 8 7 5 3
2 2 1 2 6 2

输出样例 2

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

说明

图 2：样例 2 中的国家划分。

在第二个样例中，$\bar{a} = 4$。每个国家的平均值均为 4。这给出 $S = 0$，这是一个完美的解。

子任务

你的解决方案将在 10 个测试用例上进行测试，每个测试用例最多可获得 10 分。设 $a_k$ 为国家 $k$ 中的山脉总数除以该国家的单元格数，并设 $\bar{a}$ 为整个网格中的山脉总数除以总单元格数。你想最小化以下表达式的值：

$$ S = \sum _{k=1}^{N}{(a_k - \bar{a})^2}. $$

如果 $S = 0$，你的解决方案将在该测试用例上获得 10 分。否则，你的得分将由以下表达式决定：

$$ 10 \times \max (1, \frac{S_D}{S}), $$

其中 $S_D$ 是评测系统的解决方案在同一测试用例上达到的值。