The Earth has been destroyed by a zombie virus, and only $N$ military units have survived. The Earth is a rectangular region in the coordinate plane satisfying $-10^9 \le x \le 10^9$ and $-10^9 \le y \le 10^9$. Each military unit manages a rectangular safe zone. Specifically, for $0 \le i \le N - 1$, the $i$-th military unit manages the interior and boundary of the rectangular region satisfying $A[i] \le x \le C[i]$ and $B[i] \le y \le D[i]$ as a safe zone.

Two military units are connected if there exists a point that is contained in both of their safe zones. If $0 \le i, j, k \le N - 1$, $i \neq j$, $j \neq k$, and $k \neq i$, and the $i$-th unit is connected to the $j$-th unit, and the $j$-th unit is connected to the $k$-th unit, then the $i$-th and $k$-th units are also connected. A set of military units is called a coalition if all units in the set are connected to each other, and no unit in the set is connected to any unit not in the set.

As an official at the Mars base, you need to dispatch supply ships to Earth. For efficient supply, write a function that determines all coalition information using the information about the safe zones managed by each military unit on Earth.

Implementation Details

You must implement the following function:

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

• $N$: The number of military units.
• $A, B, C, D$: Arrays of length $N$. For all $i$ ($0 \le i \le N - 1$), $A[i] \le C[i]$ and $B[i] \le D[i]$ are satisfied. The $i$-th military unit manages the rectangular region $A[i] \le x \le C[i]$, $B[i] \le y \le D[i]$ as a safe zone.
• Let $M$ be the total number of coalitions.
• This function must return an array $U$ of length $N$. For all $i$ ($0 \le i \le N - 1$), $U[i]$ is the identifier of the coalition to which the $i$-th military unit belongs.
• It must satisfy $0 \le U[i] \le M - 1$.
• For all $i, j$ ($0 \le i, j \le N - 1, i \neq j$), if $U[i] = U[j]$, then the $i$-th unit and the $j$-th unit must be connected.
• For all $i, j$ ($0 \le i, j \le N - 1, i \neq j$), if $U[i] \neq U[j]$, then the $i$-th unit and the $j$-th unit must not be connected.

You must not execute any input/output functions in any part of your submitted source code.

Examples

Input 1

3
0 0 1 1
1 1 2 2
2 -1 4 0

Output 1

0 0 1

Note

The 1st unit and the 2nd unit are connected because they share the point $(1, 1)$. On the other hand, the 3rd unit is not connected to any other unit. Therefore, there are a total of 2 coalitions; one includes the 1st and 2nd units, and the other includes only the 3rd unit. The function can return $[0, 0, 1]$. Another array the function can return is $[1, 1, 0]$.

Input 2

2
0 1 3 3
2 0 4 2

Output 2

0 0

Note

Constraints

• $1 \le N \le 500\,000$
• $-10^9 \le A[i], B[i], C[i], D[i] \le 10^9$ (for all $0 \le i \le N - 1$)
• $A[i] \le C[i]$, $B[i] \le D[i]$

Subtasks

1. (3 points) $A[i] \le i \le C[i]$, $B[i] \le 0 \le D[i]$ (for all $0 \le i \le N - 1$)
2. (4 points) $B[i] \le 0 \le D[i]$ (for all $0 \le i \le N - 1$)
3. (7 points) $N \le 5\,000$
4. (21 points) $A[i] = C[i]$ or $B[i] = D[i]$
5. (26 points) $N \le 100\,000$
6. (39 points) No additional constraints

Sample grader

The input format of the sample grader is as follows:

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

The output format of the sample grader is as follows:

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