配点 : $600$ 点

問題文

以下の条件を満たす $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$ に等しい。
• $P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}$ とする。この時、$P$ を $3$ で割った余りは $e_i$ に等しい。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$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$ が複数存在する場合、どれを出力しても良い。

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

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

No