Carpets

Interview

Time limit1sMemory limit1024 MB

Summary

Given up to three axis-aligned rectangles, find the total area of their union.

Level: Easy3 of 10
Topics: Geometry, Implementation, Math, Brute force
Solved: No attempts yet

Problem

The grandest hall of Prince Ville's new castle has a rectangular floor. Its walls run North-South and East-West. Ville's advisors have proposed covering parts of the floor with carpets and have even suggested a specific arrangement.

Caring mostly about the size of the deal, Ville wants to know the total area of the floor covered by the carpets in this arrangement. Where carpets overlap, the shared region is counted only once.

Input

The first line contains three space-separated integers $K$ , $L$ , and $P$ : the number of carpets $K$ ( $1 \le K \le 3$ ), the distance $L$ from the East wall to the West wall ( $1 \le L \le 10^6$ ), and the distance $P$ from the North wall to the South wall ( $1 \le P \le 10^6$ ).

Each of the next $K$ lines contains four space-separated integers $N$ , $S$ , $E$ , and $W$ describing one carpet. The carpet's edges are parallel to the walls, and $N$ , $S$ , $E$ , and $W$ give the distance of the carpet's North, South, East, and West edge from the corresponding wall, respectively. Carpets may overlap partially or fully. All distances are in metres.

Output

Print a single integer $S$ : the total area of the floor covered by carpets, in square metres.

Examples2

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