P14217 [ICPC 2024 Kunming I] 两星级竞赛

教育专家们出于某种原因，准备对 $n$ 项竞赛进行评级。专家们已经决定了每项竞赛的评级结果，其中第 $i$ 项竞赛被评为 $s_i$ 星级竞赛。 据说每项竞赛都会依据 $m$ 种属性进行评级，其中第 $i$ 项竞赛的第 $j$ 种属性记为 $p_{i, j}$，每种属性的取值范围从 $0$ 到 $k$（含两端）。一项竞赛的分数是其所有 $m$ 种属性的总和。也就是说，令 $v_i$ 表示第 $i$ 项竞赛的分数，我们有 $v_i = \sum\limits_{j=1}^m p_{i, j}$。 如果一项星级更高的赛事有更高的分数，看起来会比较自然。专家们要求，对于任意两项竞赛 $1 \le i, j \le n$，若 $s_i > s_j$，则必须有 $v_i > v_j$。不幸的是，专家们忘了采集一些竞赛部分（甚至全部）属性的数据。作为专家们的助手，您被要求填充这些不存在的属性值，使得上述限制条件对任意两项竞赛都成立。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入三个整数 $n$，$m$ 和 $k$（$2 \le n \le 4 \times 10^5$，$1 \le m \le 4 \times 10^5$，$n \times m \le 4 \times 10^5$，$1 \le k \le 10^9$）表示竞赛的数量，每项竞赛有几种属性，以及每种属性取值的上限。 对于接下来 $n$ 行，第 $i$ 行首先输入一个整数 $s_i$（$1 \le s_i \le 10^9$）表示第 $i$ 项竞赛被评定的星级。接下来输入 $m$ 个整数 $p_{i, 1}, p_{i, 2}, \cdots, p_{i, m}$（$-1 \le p_{i, j} \le k$）。若 $p_{i, j} = -1$ 则第 $i$ 项竞赛的第 $j$ 种属性值不存在，您需要填充该属性值；否则若 $p_{i, j} \ge 0$ 则第 $i$ 项竞赛的第 $j$ 种属性值已被给定，您不应该更改它。 保证所有数据 $n \times m$ 之和不超过 $4 \times 10^5$。

对于每组数据： 如果可以填充所有不存在的属性值并满足限制条件，首先输出一行 $\texttt{Yes}$。接下来输出 $n$ 行，第 $i$ 行包含 $m$ 个由单个空格分隔的整数 $q_{i, 1}, q_{i, 2}, \cdots, q_{i, m}$（$0 \le q_{i, j} \le k$），表示完成填充之后的第 $i$ 项竞赛的 $m$ 种属性值。若 $p_{i, j} = -1$，那么 $q_{i, j}$ 就是您填充的值；否则若 $p_{i, j} \ge 0$，那么 $q_{i, j} = p_{i, j}$。如果有多种答案，您可以输出任意一种。 如果无法满足限制条件，仅需输出一行 $\texttt{No}$。

对于第二组样例数据，即使我们将唯一的 $-1$ 填入最大的可能值 $10$，第一项竞赛的分数也只有 $15$ 分，并不大于第二项竞赛的分数 $30$ 分。