题目描述

以下の条件を満たす $N$ 行 $N$ 列の行列 $X$ が存在するかどうかを判定し、存在する場合は $1$ つ示してください。( $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$ が存在するならば $1$ 行目に Yes と出力し、$2$ 行目以降に以下の形式で $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}$

条件を満たす $X$ が複数存在する場合、どれを出力しても良い。

题目大意

给定 $N, Q$ 以及 $Q$ 条限制，存在 $N \times N$ 的 $0, 1, 2$ 矩阵（即矩阵中只能有 $0, 1, 2$），每条限制包含 $a, b, c, d, e$，表示 $[a, b]$ 行 $[c, d]$ 列的子矩阵（或者说左上角为 $(a, c)$ 右下角为 $b, d$ 的子矩阵）所有元素之积模 $3$ 后等于 $e$，你需要构造一个满足这 $Q$ 条限制的 $N \times N$ 矩阵。无解输出 No，反之输出 Yes 并输出矩阵。存在 SPJ。

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

Yes
0 2
1 2

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\ \}$
• 入力はすべて整数

Sample Explanation 1

例えば $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,3$ に対しても同様に条件を満たすことを確認できます。