문제

좀비 바이러스로 인해 지구는 멸망했고, $N$개의 군부대만이 생존하였다. 지구는 좌표공간 위에서 $-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$인 배열. 모든 $i$ ($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$를 반환해야 한다. 모든 $i$ ($0 \le i \le N-1$)에 대해, $U[i]$는 $i$번째 군부대가 속한 연합의 번호이다.
• $0 \le U[i] \le M-1$을 만족해야 한다.
• 모든 $i, j$ ($0 \le i, j \le N-1$, $i\neq j$)에 대해, $U[i] = U[j]$이면 $i$번 군부대와 $j$번 군부대가 연결되어 있어야 한다.
• 모든 $i, j$ ($0 \le i, j \le N-1$, $i \neq j$)에 대해, $U[i] \neq U[j]$이면 $i$번 군부대와 $j$번 군부대는 연결되어 있지 않아야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

예제 1

$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)을 공유하므로 연결되어 있다. 반면, 3번 군부대는 다른 어떤 군부대와도 연결되어 있지 않다. 따라서 연합은 총 2개 존재하며, 하나는 1번과 2번 군부대를 포함하고 다른 하나는 3번 군부대만을 포함한다.

함수는 [0, 0, 1]을 반환할 수 있다. 함수가 반환할 수 있는 다른 배열은 [1, 1, 0]이 있다.

예제 2

$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 \le N \le 500\,000$
• $-10^{9} \le A[i], B[i], C[i], D[i] \le 10^{9}$ (모든 $0 \le i \le N-1$)
• $A[i] \le C[i]$, $B[i] \le D[i]$

서브태스크

힌트

샘플 그레이더

Sample grader의 입력 형식은 아래와 같다.

• Line 1: $N$
• Line $2 + i$ $(0 \le i \le N-1)$: $A[i]$ $B[i]$ $C[i]$ $D[i]$

Sample grader의 출력 형식은 아래와 같다.

• Line $1$ : $U[0]$ $U[1]$ $\cdots$ $U[N-1]$

첨부

• safezone.zip