Venue Rental (Small)

Interview

Time limit2sMemory limit256 MB

Summary

Given up to 100 axis-aligned rectangles, find the area of the union of all rectangles.

Level: Medium4 of 10
Topics: Array, Implementation, Simulation, Geometry
Solved: No attempts yet

Problem

Sanghyun is about to leave for military service and wants to throw a farewell party. He rents a venue for it, and the rental company is unusual because only former programmers work there.

Once Sanghyun picks the place he wants, the company builds $N$ rectangles that cover that place completely. It then tells him the number of rectangles $N$ and, for each rectangle, the coordinates of its bottom left corner and its top right corner. The $N$ rectangles may overlap partially or completely. Every rectangle has sides parallel to the coordinate axes.

Write a program that computes the area of the venue Sanghyun rented, that is, the area of the region covered by at least one of the $N$ rectangles.

Input

The first line contains the number of rectangles $N$ ( $2 \le N \le 100$ ).

Each of the next $N$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ ( $0 \le x_1 < x_2 \le 500$ , $0 \le y_1 < y_2 \le 500$ ) separated by spaces. The bottom left corner of that rectangle is $(x_1, y_1)$ and the top right corner is $(x_2, y_2)$ .

Output

Print the area of the venue Sanghyun rented on the first line. The area is always an integer, so print it without a decimal point.

Examples6

Example 1
Input
```
3
4 2 6 3
4 0 5 1
0 0 7 8
```
Expected output
```
56
```
Example 2
Input
```
2
0 0 2 2
5 5 7 7
```
Expected output
```
8
```
Example 3
Input
```
2
1 1 4 4
1 1 4 4
```
Expected output
```
9
```
Example 4
Input
```
2
0 0 4 4
2 2 6 6
```
Expected output
```
28
```
Example 5
Input
```
2
0 0 3 3
3 0 6 3
```
Expected output
```
18
```
Example 6
Input
```
2
0 0 500 500
0 0 500 500
```
Expected output
```
250000
```