AT_tupc2024_h.12 Grid

有一个 $N \times N$ 的网格。将自上而下第 $i$ 行、自左而右第 $j$ 列的格子记为格子 $(i,j)$。

另外，给出 $M$ 个 $4$ 元组 $(t_k,i_k,j_k,d_k)\; (k=1,2,\dots,M)$。$(t,i,j,d)$ 满足以下条件：

• $t$ 是 $0$ 或 $1$。
• 若 $t=0$，则 $1 \leq i \leq N-1, 1 \leq j \leq N$。
• 若 $t=1$，则 $1 \leq i \leq N, 1 \leq j \leq N-1$。
• $d$ 是 $1$ 或 $2$。

请判断是否存在一种向网格每个格子中填写整数的方法，使得以下所有条件都成立：

• 每个格子填写的整数为 $0$ 到 $10^9$ 之间的整数。
• 上下左右相邻两个格子中填写的整数的差的绝对值为 $1$ 或 $2$。
• 对于每个 $k=1,2,\dots, M$，满足：
  • 若 $t_k=0$，则格子 $(i_k,j_k)$ 与 $(i_k+1,j_k)$ 中整数的差的绝对值为 $d_k$；
  • 若 $t_k=1$，则格子 $(i_k,j_k)$ 与 $(i_k,j_k+1)$ 中整数的差的绝对值为 $d_k$。

如果存在，请给出一个满足条件的填写方案。

输入按以下格式从标准输入读入。

$N$ $M$ $t_1$ $i_1$ $j_1$ $d_1$ $t_2$ $i_2$ $j_2$ $d_2$ $\vdots$ $t_M$ $i_M$ $j_M$ $d_M$

如果不存在任何满足条件的填写方法，请输出 No。

如果存在，请输出 $N+1$ 行。第 $1$ 行输出 Yes。第 $i+1$ $(i=1,2,\dots,N)$ 行依次输出格子 $(i,1),(i,2),\dots,(i,N)$ 填写的整数，空格分隔。

如果有多组答案，输出任意一组都可以。

样例解释 1

除此之外，

Yes
5 4
3 2

等方案也都是正确答案。

样例解释 2

除此之外，

Yes
0 2
2 1

等方案也都是正确答案。

样例解释 3

不存在满足条件的填写方法。

数据范围

• $1 \leq N \leq 1000$
• $0 \leq M \leq \min\{2 \times 10^5,2N(N-1)\}$
• $(t_k,i_k,j_k,d_k)$ 均满足题目条件
• 若 $k \neq \ell$，则 $(t_k,i_k,j_k) \neq (t_\ell,i_\ell,j_\ell)$
• 所有输入均为整数。

由 ChatGPT 5 翻译