地球被视为一个坐标空间上的矩形区域，范围为 $-10^{9} \leq x \leq 10^{9}, -10^{9} \leq y \leq 10^{9}$。每个军事基地负责管理一块矩形的安全区域。具体来说，对于 $0 \leq i \leq N-1$，第 $i$ 个军事基地管理的区域是满足 $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$ 的矩形，包括边界和内部。

如果两个军事基地的安全区域有至少一个公共点，它们就被认为是连接的。如果存在 $0 \leq i, j, k \leq N-1$，且 $i \neq j, j \neq k, k \neq i$，使得 $i$ 号基地与 $j$ 号基地连接，$j$ 号基地又与 $k$ 号基地连接，那么 $i$ 号基地和 $k$ 号基地也算连接。一个军事基地的集合，若其中所有基地互相连接，且与集合外的任何基地都不连接，这样的集合被称为一个联盟。

你是火星基地的一名官员，需要向地球派遣补给线。为了高效配送，你需要根据地球上各军事基地的安全区域信息，编写一个函数来识别所有的联盟。

实现细节

你需要实现以下函数：

vector<int> find_union(int N, vector<int> A, vector<int> B, vector<int> C, vector<int> D)

• N：军事基地的数量。
• A, B, C, D：长度为 $N$ 的数组。对于所有 $0 \leq i \leq N-1$，满足 $A[i] \leq C[i], B[i] \leq D[i]$。第 $i$ 个军事基地管理的区域为 $A[i] \leq x \leq C[i], B[i] \leq y \leq D[i]$。
• 设 $M$ 为联盟的总数。
• 函数需返回一个长度为 $N$ 的数组 $U$，其中 $U[i]$ 表示第 $i$ 个军事基地所属联盟的编号。
• 必须满足 $0 \leq U[i] \leq M-1$。
• 对于所有 $0 \leq i, j \leq N-1, i \neq j$，若 $U[i] = U[j]$，则 $i$ 号基地与 $j$ 号基地必须连接。
• 对于所有 $0 \leq i, j \leq N-1, i \neq j$，若 $U[i] \neq U[j]$，则 $i$ 号基地与 $j$ 号基地不得连接。

你提交的代码中不得包含任何输入输出函数。

样例数据

假设 $N=3$，$A=[0,1,2]$，$B=[0,1,-1]$，$C=[1,2,4]$，$D=[1,2,0]$。评测程序调用：

find_union(3, {0, 1, 2}, {0, 1, -1}, {1, 2, 4}, {1, 2, 0})

各军事基地的安全区域在坐标平面上的分布如下：

$1$ 号基地和 $2$ 号基地共享点 $(1,1)$，因此它们连接。而 $0$ 号基地与任何其他基地都不相连。所以总共有 $2$ 个联盟：一个包含 $1$ 号和 $2$ 号基地，另一个只有 $0$ 号基地。

函数可以返回 $[0,0,1]$，表示 $0$ 号基地在联盟 $0$，$1$ 号和 $2$ 号基地在联盟 $1$。另一种可能的返回值是 $[1,1,0]$。

假设 $N=2$，$A=[0,2]$，$B=[1,0]$，$C=[3,4]$，$D=[3,2]$。评测程序调用：

find_union(2, {0, 2}, {1, 0}, {3, 4}, {3, 2})

函数应返回 $[0,0]$。

子任务

对于所有输入数据，满足：

• $1 \leq N \leq 500000$
• $-10^{9} \leq A[i], B[i], C[i], D[i] \leq 10^{9}$（对于所有 $0 \leq i \leq N-1$）
• $A[i] \leq C[i], B[i] \leq D[i]$

详细子任务附加限制及分值如下表所示。

样例交互库

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$A[i]\ B[i]\ C[i]\ D[i]$

输出格式如下：

• 第 $1$ 行：$U[0]\ U[1]\ \cdots\ U[N-1]$

请注意，示例评测程序可能与实际评测程序有所不同。