题目描述

P 国的领土包含 $N\times M$ 个城市，排成 $N$ 行 $M$ 列的网格，第 $i$ 行第 $j$ 列的城市的坐标记为 $(i,j)$。

我们认为两个城市 $(i_1,j_1)$ 与 $(i_2,j_2)$ 相邻当且仅当 $|i_1-i_2|+|j_1-j_2|=1$。

国王想把城市划分为 $K$ 个省，满足以下条件：

• 每个城市恰好属于一个省；
• 每个省至少包含一个城市；
• 对于同省的两个城市，存在一条该省城市的路径以这两个城市为端点，使得路径上相邻的两个城市在网格上相邻；
• 每个城市恰好有两个相邻的城市与其同在一个省。

请你帮助国王给出划分的一个方案，若有多种方案输出任意一种均可，若无解则输出 NO。

输入格式

第一行，一个正整数 $T$，表示数据组数，之后对于每组数据：

• 一行，三个正整数 $N,M,K$。

输出格式

对于每组数据：

• 若无解则输出 NO；否则输出 YES，之后 $N$ 行，每行 $M$ 个 $[1,K]$ 的正整数，表示对应的城市被划分为哪个省。

样例

5
2 2 2
2 2 1
4 4 4
4 4 2
4 6 3

NO
YES
1 1
1 1
YES
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
YES
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
YES
1 1 1 1 1 1
1 2 2 3 3 1
1 2 2 3 3 1
1 1 1 1 1 1

数据范围与提示

对于所有数据，$K\le NM$，$\sum NM\le 2\cdot 10^5$。