题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一个二维平面上有 $N$ 个军事基地。第 $i$ 个基地的位置是坐标 $(X_i, Y_i)$。

负责该区域的补给部队打算对所有基地进行补给。每个第 $i$ 个基地可以接受补给的日期是从第 $A_i$ 天到第 $B_i$ 天之间的某一天。

由于正处于战争时期，补给部队必须保持整体从左上方向右下方推进的队形，因此只能朝右下方向前进。因此，必须为每个基地分配一个具体的补给日期 $V_i$，使得满足以下所有条件：

• 对所有的 $i$，都满足 $A_i \leq V_i \leq B_i$；
• 对所有 $i, j$ 满足 $X_i < X_j$ 且 $Y_i < Y_j$ 时，必须满足 $V_i < V_j$；
• 对所有 $i \ne j$，必须有 $V_i \ne V_j$。

给定各个基地的位置 $(X_i, Y_i)$ 以及它们可接受补给的日期范围 $[A_i, B_i]$，请编写一个程序判断是否存在一种补给日期的分配方案，满足上述所有条件。如果存在，输出 YES，并按基地编号顺序输出每个基地的分配日期；如果不存在，输出 NO。

下图展示了一个包含 6 个基地的示例情况。图中的每个点代表一个基地，点的右上方标注了该基地可以接受补给的日期范围。

下图还展示了为这些基地安排补给日期的一个可行方案，点的右下方标注了分配给每个基地的具体补给日期。图中弯曲的线表示补给部队在第 2 天至第 3 天之间可能处于的位置范围。

输入格式

第一行输入一个整数 $N$，表示基地的数量。

接下来 $N$ 行，每行输入四个整数 $X_i$, $Y_i$, $A_i$, $B_i$，以空格分隔，表示第 $i$ 个基地的位置和其可接受补给的日期范围。

输出格式

如果存在合法的补给方案，第一行输出 YES，第二行输出 $N$ 个整数，表示按基地编号顺序分配的补给日期，数与数之间以空格分隔。

如果不存在合法的补给方案，输出 NO。

6
2 6 1 3
4 1 4 6
6 5 4 6
1 3 2 5
3 2 1 3
5 4 1 6

YES
3 4 6 2 1 5

2
1 1 2 2
2 2 1 1

NO

提示

约束条件

• 所有给定的数都是整数。
• $1 \leq N \leq 250\,000$
• $1 \leq A_i \leq B_i \leq N$
• $1 \leq X_i \leq N$
• $1 \leq Y_i \leq N$
• 所有 $X_i$ 互不相同，即 $i \ne j$ 时 $X_i \ne X_j$
• 所有 $Y_i$ 互不相同，即 $i \ne j$ 时 $Y_i \ne Y_j$

子任务

1. （13 分）$N \leq 10$
2. （18 分）$N \leq 2\,500$
3. （22 分）对所有 $i$，满足 $B_i = N$
4. （47 分）无附加限制