Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21621. 【PR #2】划分

Statistics

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]$ 的正整数,表示对应的城市被划分为哪个省。

样例

input

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

output

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$。

子任务编号 特殊限制 分值
$1$ $N,M\le 4$ $5$
$2$ $N\le 4$ $6$
$3$ $N\le 6$ $10$
$4$ $N=M$ $18$
$5$ $K$ 在 $[1,NM]\cap\mathbb N$ 中独立均匀随机生成 $39$
$6$ $ $ $22$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$