题目背景

译自 9th Romanian Master of Informatics, RMI 2021 D1T1。$\texttt{1s,0.5G}$。

题目描述

Madoka 要在 $N$ 行 $M$ 列的矩形格子内种花，每个格子内种一株花。一共有 $K$ 种品种的花，编号为 $1\sim K$。

Madoka 认为，为了让花更好看，以下条件必须满足：

• 每种花至少出现一株。
• 每种花所在的格子形成一个四连通块。
• 与格子 $(i,j)$ 四连通的格子中，恰好有两个格子种的花与 $(i,j)$ 种的花的品种相同。

请你帮她构造一组方案，或者指出这是不可能实现的。

输入格式

本题单个测试点内有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。

接下来 $T$ 组测试数据，每组测试数据包含一行三个正整数 $N,M,K$。

输出格式

对于每组测试数据：

• 如果不可能构造，输出一行一个 $\texttt{NO}$；
• 否则，输出一行一个 $\texttt{YES}$；接下来 $N$ 行，每行 $M$ 个正整数，描述一个方案。

任意一组合法方案都可以得分。

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

提示

对于 $100\%$ 的数据，保证：

• $1\le N,M\le 2\times 10^5$；
• $1\le K\le N\cdot M$；
• $1\le T\le 10^5$；
• 令 $S$ 为有解的测试数据中的 $\sum N\cdot M$，则 $S\le 2\times 10^5$。

• 特殊性质 A：$M\le 4$。
• 特殊性质 B：$N=M$。
• 特殊性质 C：$K$ 在 $[1,N\cdot M]$ 中等概率独立随机选取。