Territories

Time limit9sMemory limit1024 MB

Summary

Each territory can be placed in four ways on the torus. Find the largest area common to all territories after choosing one placement for each.

Level: Hard9 of 10
Topics: Segment tree, Intervals, Sorting
Solved: No attempts yet

Statement

Bajtazar is a biologist studying the fauna of a newly discovered planet. He has observed that the planet is home to $n$ distinct species of unique animals. Geologists have also found huge mineral deposits there, and plans call for large mines that could threaten the planet's ecological balance.

Every species on the planet is territorial: each one has a fixed rectangle in which it can move. To reassure the biologists, the Interplanetary Parliament issued a decree that any area lying inside the territories of all species will become a nature reserve, so no mines will be built there.

For each species, Bajtazar recorded the coordinates $(x_1, y_1)$ and $(x_2, y_2)$ of two opposite corners of its territory. He has now returned to Earth and is analyzing the data to determine the size of the reserve.

The planet is a torus, and its map is a grid of size $X \times Y$ with a coordinate system. Points are written as $(x, y)$ with $0 \le x < X$ and $0 \le y < Y$ . All territories are rectangles with sides parallel to the coordinate axes.

Because the planet is a torus, two opposite corners do not determine a unique rectangle. Each species has four possible territories. Parliament wants to know as soon as possible how many mines can definitely be built, so Bajtazar must find the largest possible area of the reserve from the given data.

Input

The first line contains three integers $n$ , $X$ , and $Y$ ( $1 \le n \le 500\,000$ , $2 \le X, Y \le 10^9$ ), the number of species and the map size. Each of the next $n$ lines contains four integers $x_1, y_1, x_2, y_2$ ( $0 \le x_1, x_2 < X$ , $0 \le y_1, y_2 < Y$ , $x_1 \ne x_2$ , $y_1 \ne y_2$ ), the coordinates of two opposite corners of a species' territory.

Output

Print one integer: the maximum possible area of the intersection of all territories.

Hint

The figure shows three of the 16 possible placements of two territories, given corners $(2, 1)$ , $(8, 6)$ and $(5, 2)$ , $(4, 4)$ on a $10 \times 7$ map. The intersections have areas 0, 8, and 15. The last figure shows the largest possible reserve. The reserve does not need to be connected.

Examples1

Example 1
Input
```
2 10 7
2 1 8 6
5 2 4 4
```
Expected output
```
15
```