题目描述

题目译自 Romanian Master of Informatics 2021 Day1 T1 「Gardening」

高地女巫阿兹莎想和她的朋友莱卡一起做一件有趣的事情：种花。她们想做一个长 $N$ 米，宽 $M$ 米的矩形花园。花园被分成 $1 \times 1$ 米的方块。问题是：她们应该种什么花？

莱卡找到了 $K$ 种不同的花。阿兹莎和莱卡将在每个 $1\times 1$ 的方块中种一种花。此外，为了美观，花园必须满足以下条件：

1. 每种花都必须在花园中至少出现一次。
2. 对于任何两个种植相同类型花的方块，必须存在一条路径连接它们，其中路径上所有方块都种植相同类型的花。例如，以下花园是不合法的：
3. 任何方块都必须有且只有两个相邻的方块种植相同类型的花。例如，以下花园是不合法的：

请注意，在上述条件中，我们称两个方块是相邻的，当且仅当它们共享一条公共边（不仅仅是一个角）；而一条路径是一系列相邻方块的序列。

给定 $T$ 个不同的 $N, M$ 和 $K$ 的值。帮助阿兹莎和莱卡规划一个满足条件的花园，或者告诉她们这是不可能的。

输入格式

输入包含多组数据。第一行包含一个整数 $T$。接下来的 $T$ 行每行描述了一组测试数据，每组测试数据包含三个整数 $N, M, K$。

输出格式

按顺序输出每组测试数据的答案。对于一组测试数据，如果不存在解决方案，则在一行上输出 NO。否则，首先在一行上输出 YES，然后输出 $N \times M$ 个整数，排列成 $N$ 行和 $M$ 列，描述所需的花园。输出的行和列对应于花园的行和列，每个整数对应于一个 $1\times 1$ 的方块。整数代表种植在方块中的花类型，其中类型从 $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

对于第一组测试数据，我们注意到没有 $2\times 2$ 的花园可以用 $2$ 种花。因此我们输出 NO。其他花园如下图所示：

数据范围与提示

对于所有输入数据，满足：

• $1 \leq T \leq 10^5$
• $1 \leq N, M \leq 2\cdot 10^5$。
• $1 \leq K \leq N \times M$。
• 令 $S$ 等于所有测试数据组中其中存在答案（即输出不是 NO）的 $N \times M$ 的总和。
• $S \leq 2\cdot 10^5$。

详细子任务附加限制及分值如下表所示。