Problem Description

Find the union area of $n$ rectangles whose sides are parallel to the coordinate axes.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain four non-negative integers $x_1, y_1, x_2, y_2$, indicating that the four vertices of a rectangle are $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_2)$, $(x_2, y_1)$.

Output Format

Output one positive integer in a single line, representing the total area covered by the union of the $n$ rectangles.

2
100 100 200 200
150 150 250 255

18000

Hint

For $20\%$ of the testdata, $1 \le n \le 1000$.
For $100\%$ of the testdata, $1 \le n \le {10}^5$, $0 \le x_1 < x_2 \le {10}^9$, $0 \le y_1 < y_2 \le {10}^9$.

Updated on 4.10 by Dengduck (kouhu) & yummy (implementation): one more test case was added.

Translated by ChatGPT 5