Coverage Area of Axis-Aligned Rectangles

Given a set of axis-aligned rectangles in the plane, each rectangle is defined by its bottom-left and top-right coordinates. A point is considered covered by a rectangle if it lies within the rectangle or on its boundary.

Your task is to compute two areas:

• The total area of points that are covered by an odd number of rectangles.
• The total area of points that are covered by an even number (with at least 2 coverings) of rectangles.

Formally, let a point be covered by an odd number of rectangles if the number of rectangles covering it is odd, and by an even number (with at least 2) if the number of coverings is even and at least 2.

Note: Areas which are not covered or covered by only one rectangle (an odd count) should only contribute to the odd coverage area.

It is recommended to use coordinate compression and a 2D difference array (or prefix sum) technique to solve this problem.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 1000) representing the number of rectangles. Each of the following n lines contains four integers x1 y1 x2 y2, denoting the bottom-left and top-right coordinates of a rectangle (x1 < x2 and y1 < y2).

outputFormat

Output two numbers separated by a space: the total area covered by an odd number of rectangles and the total area covered by an even number (at least 2) of rectangles.

sample

1
0 0 1 1

1 0