Problem Description

A group of archaeological robots on Planet X are working on a ruin.

The ground in this area is hard as stone and flat as a mirror.

For convenience, the managers set up a standard Cartesian coordinate system.

Each robot has its own specialty and unique skills, and they are interested in different things.

After various measurements, each robot will report one or more rectangular regions as priority areas for excavation.

A rectangle is given in the format $(x_1,y_1,x_2,y_2)$, representing the coordinates of two opposite corners of the rectangle.

To make them eye-catching, the headquarters requires all rectangles selected by the robots to be painted yellow.

Xiaoming does not need to be a painter; he just needs to calculate how much paint will be used in total.

This is not hard: just compute the total area covered by all rectangles.

Note that rectangles may overlap.

Given several rectangles as input, output the total area covered by them.

Input Format

The first line contains an integer $n$, the number of rectangles $(1 \le n<10000)$.

The next $n$ lines each contain $4$ integers $x_1$, $y_1$, $x_2$, $y_2$, separated by spaces, representing the coordinates of two opposite corners of a rectangle.

$(0 \le x_1,y_1,x_2,y_2 \le 10000)$.

Output Format

Output one integer in one line, the total area covered by the rectangles.

3
1 5 10 10
3 1 20 20
2 7 15 17

340

3
5 2 10 6
2 7 12 10
8 1 15 15

128

Hint

Lanqiao Cup 2022 Provincial Contest A Group Problem J.

Translated by ChatGPT 5