构造矩阵

题目描述

判断是否存在满足以下条件的 $N \times N$ 矩阵 $X$,若存在则给出一个这样的矩阵。(设 $x_{i,j}$ 为 $X$ 中从上数第 $i$ 行、从左数第 $j$ 列的元素。)

对于每个 $i$ 和 $j$ $(1 \leq i,j \leq N)$,$x_{i,j} \in \{ 0,1,2 \}$。

以下条件对每个 $i=1,2,\ldots,Q$ 成立。

设 $P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$。则 $P$ 模 $3$ 与 $e_i$ 同余。

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$a_1$ $b_1$ $c_1$ $d_1$ $e_1$
$\vdots$
$a_Q$ $b_Q$ $c_Q$ $d_Q$ $e_Q$

输出格式

如果不存在满足条件的矩阵 $X$,输出 No。

如果存在满足条件的矩阵 $X$,第一行输出 Yes,并在第二行及以后按以下格式输出一个这样的 $X$。

$x_{1,1}$ $x_{1,2}$ $\ldots$ $x_{1,N}$
$x_{2,1}$ $x_{2,2}$ $\ldots$ $x_{2,N}$
$\vdots$
$x_{N,1}$ $x_{N,2}$ $\ldots$ $x_{N,N}$

如果存在多个满足条件的矩阵,任意一个都会被接受。

样例

2 3
1 1 1 2 0
1 2 2 2 1
2 2 1 2 2

Yes
0 2
1 2

例如,对于 $i=2$,有 $P = \prod_{a_2 \leq j \leq b_2} \prod_{c_2 \leq k \leq d_2} x_{j,k}= \prod_{1 \leq j \leq 2} \prod_{2 \leq k \leq 2} x_{j,k}=x_{1,2} \times x_{2,2}$。

在该样例输出中,$x_{1,2}=2$ 且 $x_{2,2}=2$,所以 $P=2 \times 2 = 4$,模 $3$ 与 $e_2=1$ 同余。

可以类似地验证 $i=1$ 和 $i=3$ 的条件也得到满足。

4 4
1 4 1 4 0
1 4 1 4 1
1 4 1 4 2
1 4 1 4 0

No

数据范围

• $1 \leq N,Q \leq 2000$
• $1 \leq a_i \leq b_i \leq N$
• $1 \leq c_i \leq d_i \leq N$
• $e_i \in \{0,1,2 \}$
• 输入中的所有值均为整数。

提示

答案不唯一,输出任意合法解即可。