Given a set of $N$ axis-aligned rectangles in the plane, find the area of regions which are covered by at least one rectangle.

Constraints

* $ 1 \leq N \leq 2000 $
* $ −10^9 \leq x1_i < x2_i\leq 10^9 $
* $ −10^9 \leq y1_i < y2_i\leq 10^9 $

Input

The input is given in the following format.

$N$
$x1_1$ $y1_1$ $x2_1$ $y2_1$
$x1_2$ $y1_2$ $x2_2$ $y2_2$
:
$x1_N$ $y1_N$ $x2_N$ $y2_N$


($x1_i, y1_i$) and ($x2_i, y2_i$) are the coordinates of the top-left corner and the bottom-right corner of the $i$-th rectangle respectively.

Output

Print the area of the regions.

Examples

Input

2
0 0 3 4
1 2 4 3


Output

13


Input

3
1 1 2 5
2 1 5 2
1 2 2 5


Output

7


Input

4
0 0 3 1
0 0 1 3
0 2 3 3
2 0 3 3


Output

8
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;
using block = tuple<int, int, int, int>;

int N;
vector<int> X, Y;
vector<int> Y_posi[5000], Y_nega[5000]; 
vector<block> points;
vector<int> grid;

int main()
{
    // read input
    scanf("%d", &N);
    rep(i, 0, N)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        points.emplace_back(x1, y1, x2, y2); 
        X.emplace_back(x1);
        X.emplace_back(x2);
        Y.emplace_back(y1);
        Y.emplace_back(y2);
    }

    // make compressed axes
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());

    // paint corner
    for (block point: points)
    {
        int x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = point;

        x1 = lower_bound(X.begin(), X.end(), x1) - X.begin();
        x2 = lower_bound(X.begin(), X.end(), x2) - X.begin();
        y1 = lower_bound(Y.begin(), Y.end(), y1) - Y.begin();
        y2 = lower_bound(Y.begin(), Y.end(), y2) - Y.begin();

        Y_posi[y1].push_back(x1);
        Y_posi[y1].push_back(x2);
        Y_nega[y2].push_back(x1);
        Y_nega[y2].push_back(x2);
    }

    long long ans = 0;
    vector<int> grid(X.size(), 0);
    rep(y, 0, (int)Y.size()-1)
    {
        // paint upper line
        for (int i=0; i < (int) Y_posi[y].size(); i += 2)
        {
            int from  = Y_posi[y][i];
            int to = Y_posi[y][i+1];
            
            rep(x, from, to) ++grid[x];
        }

        // paint bottom line
        for (int i=0; i < (int) Y_nega[y].size(); i += 2)
        {
            int from  = Y_nega[y][i];
            int to = Y_nega[y][i+1];
            
            rep(x, from, to) --grid[x];
        }

        // take cumulative sum 
        rep(x, 0, (int)X.size())
        {
            if (grid[x] == 0) continue;
            
            ans += (ll) (Y[y+1]-Y[y]) * (X[x+1]-X[x]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

