仪式广场

城市建成后，人们举行了仪式来赞美光芒。小灯布置在村庄广场的各处，每一盏灯都散发着独特而柔和的光芒。

现在，仪式的下一阶段开始了。每盏灯都开始沿着选定的路径行进，将光芒洒向未知的空间。它们的移动必须经过精心编排，确保路径互不交叉——每盏灯都必须以自己安静的节奏流动。

追寻它们曾经描绘的轨迹，重现光芒向外扩散的那一刻。

广场的地面表示为一个具有 $H$ 行和足够多列的网格。从上往下数第 $r$ 行、从左往右数第 $c$ 列的单元格记为 $(r, c)$。

岛上的居民在这个网格上放置了 $N$ 个光源。作为仪式的一部分，每个光源必须向右移动（即向列号增加的方向）指定的距离。

由于同步光源移动的复杂性，必须遵守以下几个约束条件：

• 每个光源都固定在一个 $1 \times 1$ 的正方形瓷砖中心。
• 这 $N$ 块瓷砖必须各自移动一个介于 $1$ 到 $N$ 之间且互不相同的整数距离。
• 所有 $N$ 块瓷砖同时开始移动，以恒定的速度行进，并且必须同时到达目的地。
• 在移动过程中的任何时刻，瓷砖之间都不能重叠（但允许边缘接触）。
• 所有移动完成后，任意两个光源不能结束在同一列。

例如，考虑 $H = 2$ 且 $N = 4$，光源的初始位置为 $(1, 1), (1, 3), (2, 2), (2, 3)$。在下图中，每个光源瓷砖用一个彩色正方形表示。

如果我们为这些光源分配以下移动距离，则上述所有条件均得到满足：

下图是这些光源在三个时间点的视觉表示：起点、移动的中点以及最终位置。

你的任务是确定是否可以为这些光源分配移动距离，使得满足所有给定的条件。如果可以，请提供一种有效的分配方案。

输入格式

第一行包含两个空格分隔的整数 $H$ 和 $N$。

接下来的 $N$ 行，每行包含两个空格分隔的整数 $r_i$ 和 $c_i$，表示第 $i$ 个光源的初始位置为 $(r_i, c_i)$。

数据范围

• $1 \le H \le 10^9$
• $2 \le N \le 2 \times 10^5$
• $1 \le r_i \le H$ （$1 \le i \le N$）
• $1 \le c_i \le 10^9$ （$1 \le i \le N$）
• $(r_i, c_i) \neq (r_j, c_j)$ （$1 \le i < j \le N$）

输出格式

如果可以分配移动距离以满足所有条件，在第一行输出 YES。

在第二行输出 $N$ 个空格分隔的整数 $B_1, B_2, \dots, B_N$，其中 $B_i$ 表示第 $i$ 个光源应该向右移动的距离。如果存在多个有效解，输出其中任意一个。

如果不可能，在单行中输出 NO。

子任务

• 子任务 1（12 分）：$N \le 9$
• 子任务 2（5 分）：$c_1 = c_2 = \dots = c_N$
• 子任务 3（32 分）：$H = 1, N \le 1000$
• 子任务 4（11 分）：$H = 1$
• 子任务 5（40 分）：无附加限制。

样例

输入样例 1

2 4
1 1
1 3
2 2
2 3

输出样例 1

YES
2 1 3 4

输入样例 2

10 3
7 1000000000
9 1000000000
3 1000000000

输出样例 2

YES
2 1 3

输入样例 3

1 5
1 1
1 3
1 5
1 7
1 9

输出样例 3

YES
5 4 3 2 1