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) $ に書き込む整数をこの順に空白区切りで出力せよ。 解が複数存在する場合、どれを出力しても良い。

### Sample Explanation 1 他にも、 ``` Yes 5 4 3 2 ``` なども正解になります。 ### Sample Explanation 2 他にも、 ``` Yes 0 2 2 1 ``` なども正解になります。 ### Sample Explanation 3 条件を満たす書き込み方は存在しません。 ### Constraints - $ 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) $ - 入力はすべて整数