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 M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

template<typename T>
static inline void chmin(T& ref, const T  value) {
    if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
    if (ref < value) ref = value;
}

struct Compressed {
    map<ll, ll> zip;
    vector<ll> unzip;

    int compress(vector<ll>& x) {
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        unzip.resize(x.size());
        for (int i = 0; i < x.size(); i++) {
            zip[x[i]] = i;
            unzip[i] = x[i];
        }
        return x.size();
    }
};

int main() {
    int n;
    cin >> n;
    vector<t4> rs(n);
    vector<ll> xs, ys;
    rep(i, n) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        rs[i] = tie(x1, y1, x2, y2);
        xs.push_back(x1);
        ys.push_back(y1);
        xs.push_back(x2);
        ys.push_back(y2);
    }
    Compressed xc, yc;
    xc.compress(xs);
    yc.compress(ys);
    vector<vector<int>> imos(yc.unzip.size(), vector<int>(xc.unzip.size(), 0));
    rep(i, n) {
        ll x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = rs[i];
        imos[yc.zip[y1]][xc.zip[x1]]++;
        imos[yc.zip[y1]][xc.zip[x2]]--;
        imos[yc.zip[y2]][xc.zip[x1]]--;
        imos[yc.zip[y2]][xc.zip[x2]]++;
    }
    vector<vector<int>> sum(yc.unzip.size(), vector<int>(xc.unzip.size(), 0));
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (x == 0) {
                sum[y][x] = imos[y][x];
            }
            else {
                sum[y][x] = sum[y][x - 1] + imos[y][x];
            }
        }
    }
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (y < yc.unzip.size() - 1) {
                sum[y + 1][x] += sum[y][x];
            }
        }
    }
    ll area = 0;
    for (int y = 0; y < yc.unzip.size(); y++) {
        for (int x = 0; x < xc.unzip.size(); x++) {
            if (sum[y][x] != 0) {
                ll dy = yc.unzip[y + 1] - yc.unzip[y];
                ll dx = xc.unzip[x + 1] - xc.unzip[x];
                area += dy * dx;
            }
        }
    }
    cout << area << endl;
    return 0;
}

