有一个 $N \times N$ 的网格。第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。 给定 $M$ 个整数元组 $(t_k, i_k, j_k, d_k)$ ($k = 1, 2, \dots, M$)。每个元组 $(t, i, j, d)$ 满足以下条件：

• $t$ 为 $0$ 或 $1$。
• 若 $t = 0$，则 $1 \le i \le N - 1$ 且 $1 \le j \le N$。
• 若 $t = 1$，则 $1 \le i \le N$ 且 $1 \le j \le 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$

• $1 \le N \le 1000$
• $0 \le M \le \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)$。
• 所有输入值均为整数。

输出格式

如果无法满足条件填满网格，输出 No。 如果可能，输出 $N + 1$ 行。第一行输出 Yes。第 $i + 1$ 行（$i = 1, 2, \dots, N$）按顺序输出单元格 $(i, 1), (i, 2), \dots, (i, N)$ 中填入的整数，以空格分隔。 如果存在多种答案，输出任意一种即可。

样例

样例 1

输入

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

输出

Yes
0 1
2 3

样例 2

输入

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

输出

Yes
0 2
2 3

样例 3

输入

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

输出

No

说明

对于第一个样例，

Yes
5 4
3 2

也可以作为一组解。

对于第二个样例，

Yes
0 2
2 1

也可以作为一组解。

对于第三个样例，不存在合法的配置。