It is time to paint the apartment again. Bajtazar does not like painting, but he noticed that the paint containers and brushes sparked lively interest among his children. So, he handed out the brushes to his children and asked them to paint one of the walls. Each child painted a rectangular fragment with sides parallel to the coordinate axes.

Unfortunately, it turned out that the paint purchased by Bajtazar is not of the best quality, so only those fragments of the wall that were painted by at least $n - 1$ children look good now. What is the total area of these fragments?

Input

The first line of the input contains an integer $n$ ($2 \le n \le 500\,000$), representing the number of Bajtazar's children.

Each of the next $n$ lines describes the area painted by one child. The $i$-th of these lines contains four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ ($0 \le x_{1} < x_{2} \le 10^{9}$, $0 \le y_{1} < y_{2} \le 10^{9}$). These denote that the $i$-th child painted an area that is a rectangle with its bottom-left corner at $(x_{1}, y_{1})$, its top-right corner at $(x_{2}, y_{2})$, and sides parallel to the coordinate axes.

Output

Your program should output a single integer — the area of the part of the wall that does not require further painting, that is, the part that was painted by at least $n - 1$ children.

Examples

Input 1

3
0 0 5 5
1 0 2 5
0 1 6 3

Output 1

13

Note

The result includes the areas painted in the drawing with the darker and darkest colors.