CF659F Polycarp and Hay

农夫 Polycarp 有一个堆放干草的仓库，可以表示为一个 $n \times m$ 的矩形表格，其中 $n$ 表示行数，$m$ 表示列数。表格的每个单元格都堆放着一堆干草。在第 $i$ 行第 $j$ 列的草垛的高度为整数 $a_{i,j}$，也就是该草垛含有的干草体积为 $a_{i,j}$ 立方米，因为所有格子的底面积均为 $1 \times 1$。 Polycarp 决定整理仓库，可以从每一堆的顶部移走任意整数立方米的干草。不同草垛可以移走不同数量，也可以完全不动或直接全部移走（此时该格变为空，不再有草垛）。 Polycarp 希望整理后的仓库满足以下要求： - 剩余干草的总量等于 $k$； - 所有剩下的草垛高度（即非零的格子）都相等； - 至少有一个草垛的高度保持不变（即完全未动）； - 剩余的草垛必须形成一个连通区域，以保持结构的稳定性。 当两个草垛在表格中共享一条边时，称它们是相邻的。如果能从一个草垛出发，仅通过移动到相邻草垛，最终能到达连通区域内任意其他草垛，则该区域被称为连通区域。在此情况下，所有相邻的草垛必然属于同一个区域。 请你帮助 Polycarp 完成这个艰巨的任务，或者告知是否无法实现。

输入的第一行为三个整数 $n$、$m$ ($1 \leq n, m \leq 1000$) 和 $k$ ($1 \leq k \leq 10^{18}$)，表示表格的行数、列数以及整理后总共需要留下的干草体积。 接下来的 $n$ 行，每行包含 $m$ 个正整数 $a_{i,j}$ ($1 \leq a_{i,j} \leq 10^9$)，表示第 $i$ 行第 $j$ 列堆放的干草体积。

如果 Polycarp 可以完成整理，在第一行输出 "YES"（不含引号），否则输出 "NO"（不含引号）。 如果输出 "YES"，接下来输出 $n$ 行，每行 $m$ 个数，表示整理后各格子的草垛高度。所有保留下来的非零草垛高度应相等且连成一片，至少有一个格子的高度与初始相同，其他格子的高度全为零。 如有多组可行解，输出任意一种。

在第一个样例中，所有非零的格子组成了一个连通区域，且它们的高度都等于 $7$，没有超过原始草垛的高度，区域的格子数量为 $5$，因此总干草体积为 $k = 7 \times 5 = 35$。其中第 $2$ 行第 $3$ 列的草垛高度未做改动。 由 ChatGPT 5 翻译