Rectangles

Time limit2sMemory limit512 MB

Summary

Given up to 100,000 axis-aligned rectangles drawn by XOR-flipping pixels on a white field, find the total count of black pixels.

Level: Hard8 of 10
Topics: Segment tree, Prefix sum, Sorting, Geometry
Solved: No attempts yet

Problem

You are working on a new graphics system, which has added a new feature. Whenever you draw a figure, all the pixels in that figure flip from white to black, or from black to white. This image is what happens when three overlapping rectangles are drawn on a white field:

Starting with a white field, given a series of axis-aligned rectangles, how many pixels end up black?

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.

Each test case will begin with a line with a single integer n (1 ≤ n ≤ 100,000) indicating the number of rectangles.

Each of the next n lines will have four space-separated integers x1, y1, x2 and y2 (0 ≤ x1 < x2 ≤ 10^9, 0 ≤ y1 < y2 ≤ 10^9) which represent opposite corners of a rectangle. The rectangle consists of all pixels (x,y) such that x1 ≤ x < x2 and y1 ≤ y < y2, so the area of the rectangle is (x2 - x1) × (y2 - y1) pixels.

Output

Output a single integer, which is the number of pixels that are black after all of the rectangles are drawn on a white field.

Examples2

Example 1
Input
```
2
0 0 4 4
1 1 3 3
```
Expected output
```
12
```

Example 2

Input

Expected output