Mars Map

Time limit1sMemory limit128 MB

Summary

Compute the total area covered by the union of up to 10,000 axis-aligned rectangles.

Level: Medium6 of 10
Topics: Segment tree, Sorting, Geometry
Solved: No attempts yet

Problem

In 2051, the ambitiously launched Mars probe Seonghwa sent back N maps of the regions it surveyed.

Encouraged by the probe's success, the space agency announced an ambitious plan to complete a map of the entire surface of Mars.

Before building the full map, all of the maps the probe has sent so far were overlaid and merged into one. What is the area of the region actually covered by this merged map?

Each map sent by the probe is always an axis-aligned rectangle, and the maps may overlap.

Input

The first line contains the number of maps N (1 ≤ N ≤ 10,000) sent by the probe.

Each of the next N lines describes one map with four integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000). (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. Every rectangle's sides are parallel to the x-axis or the y-axis.

Output

Print, on the first line, the total area of the region covered when all maps sent so far are overlaid and merged together.

Hint

This asks for the area of the union of several rectangles. Sweeping a vertical line across the x-axis, together with coordinate compression on the y values and a segment tree, solves it in O(N log N).

Examples4

Example 1
Input
```
2
10 10 20 20
15 15 25 30
```
Expected output
```
225
```
Example 2
Input
```
1
0 0 10 10
```
Expected output
```
100
```
Example 3
Input
```
2
0 0 10 10
20 20 30 30
```
Expected output
```
200
```
Example 4
Input
```
2
0 0 10 10
10 0 20 10
```
Expected output
```
200
```