Rectangles

Time limit3sMemory limit128 MB

Summary

Given N axis-aligned rectangles, compute the area of their union.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Prefix sum
Solved: No attempts yet

Problem

There are $N$ axis-aligned rectangles placed on the plane. Write a program that computes the total area of the region covered by these rectangles. A region covered by several rectangles at once is counted only once.

Input

The first line contains a positive integer $N$ . ( $1 \le N \le 200{,}000$ )

Each of the next $N$ lines contains four integers $x_1$ , $x_2$ , $y_1$ , $y_2$ separated by spaces, describing the rectangle $[x_1, x_2] \times [y_1, y_2]$ .

All coordinates are integers with $0 \le x_1 < x_2 \le 10^9$ and $0 \le y_1 < y_2 \le 10^9$ .

Output

Print the total area of the region covered by the $N$ rectangles.

Examples2

Example 1
Input
```
2
0 3 1 2
1 2 0 3
```
Expected output
```
5
```
Example 2
Input
```
1
0 5 0 4
```
Expected output
```
20
```