問題文

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 である

制約

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

入力例 1

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

出力例 1

Yes
0 1
2 3

他にも、

Yes
5 4
3 2

なども正解になります。

入力例 2

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

出力例 2

Yes
0 2
2 3

他にも、

Yes
0 2
2 1

なども正解になります。

入力例 3

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

出力例 3

No

条件を満たす書き込み方は存在しません。