Problem Description

There are some rectangles on the plane, and both of their sides are parallel to the coordinate axes.

We say that a point is covered by a rectangle if the point lies inside the rectangle or on its boundary.

Find the areas of the regions covered by an odd number of rectangles, and covered by an even number $(\geq 2)$ of rectangles, respectively.

Input Format

The first line contains an integer $n$, which denotes the number of rectangles.

The next $n$ lines describe the rectangles. The $i$-th line contains four integers $l_{i}, b_{i}, r_{i}, t_{i}$, meaning that the two diagonal corners of the rectangle are $\left(l_{i}, b_{i}\right)$ and $\left(r_{i}, t_{i}\right)$.

Output Format

Output two lines.

The first line contains an integer, the area of the region covered by an odd number of rectangles.

The second line contains an integer, the area of the region covered by an even number $(\geq 2)$ of rectangles.

3
1 1 3 3
2 2 4 4
3 3 5 5

8
2

Hint

For $20\%$ of the test cases, $1 \leq n \leq 10$, $0 \leq l_{i}\le r_{i} \leq 100$, $0 \leq b_{i}\le t_{i} \leq 100$.

For $40\%$ of the test cases, $1 \leq n \leq 1000$, $0 \leq l_{i}\le r_{i} \leq 100$, $0 \leq b_{i}\le t_{i} \leq 100$.

For $60\%$ of the test cases, $1 \leq n \leq 10000$, $0 \leq l_{i}\le r_{i} \leq 1000$, $0 \leq b_{i}\le t_{i} \leq 1000$.

For $80\%$ of the test cases, $1 \leq n \leq 10^5$, $0 \leq l_{i}\le r_{i} \leq 10^5$, $0 \leq b_{i}\le t_{i} \leq 10^5$.

For all test cases, $1 \leq n \leq 10^5$, $0 \leq l_{i}\le r_{i} \leq 10^{9}$, $0 \leq b_{i}\le t_{i} \leq 10^{9}$.

Lanqiao Cup 2020 National Contest, Group A, Problem I.

Translated by ChatGPT 5