CSES 1741 ↗

Area of Rectangles

Total area covered by the union of axis-aligned rectangles.

0
submissions
—
best score

Given n rectangles, your task is to determine the total area of their union.

Input

The first line has an integer n: the number of rectangles.

After that, there are n lines describing the rectangles. Each line has four integers x1, y1, x2 and y2: a rectangle begins at point (x1,y1) and ends at point (x2,y2).

Output

Print the total area covered by the rectangles.

Constraints

  • 1≤n≤105
  • −106≤x1<x2≤106
  • −106≤y1<y2≤106

Example

Input:

3
1 3 4 5
3 1 7 4
5 3 8 6

Output:

24

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AreaOfRectangles/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.