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 翻译