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 <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>

using namespace std;

/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
*/

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll n;
    cin >> n;
    vll x1(n), y1(n), x2(n), y2(n);
    vll xv, yv;
    for(ll i = 0; i < n; i++) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        xv.push_back(x1[i]);
        xv.push_back(x2[i]);
        yv.push_back(y1[i]);
        yv.push_back(y2[i]);
    }
    sort(xv.begin(), xv.end());
    sort(yv.begin(), yv.end());
    xv.erase(unique(xv.begin(), xv.end()), xv.end());
    yv.erase(unique(yv.begin(), yv.end()), yv.end());
    
    vvll plain(yv.size(), vll(xv.size()));
    for(ll i = 0; i < n; i++) {
        ll xi1 = lower_bound(xv.begin(), xv.end(), x1[i]) - xv.begin();
        ll xi2 = lower_bound(xv.begin(), xv.end(), x2[i]) - xv.begin();
        ll yi1 = lower_bound(yv.begin(), yv.end(), y1[i]) - yv.begin();
        ll yi2 = lower_bound(yv.begin(), yv.end(), y2[i]) - yv.begin();
        plain[yi1][xi1]++;
        plain[yi2][xi2]++;
        plain[yi1][xi2]--;
        plain[yi2][xi1]--;
    }
    for(ll i = 0; i < yv.size() - 1; i++) {
        for(ll j = 0; j < xv.size(); j++) {
            plain[i + 1][j] += plain[i][j];
        }
    }
    for(ll i = 0; i < yv.size(); i++) {
        for(ll j = 0; j < xv.size() -  1; j++) {
            plain[i][j + 1] += plain[i][j];
        }
    }
    ll ans = 0;
    for(ll i = 0; i < yv.size() - 1; i++) {
        for(ll j = 0; j < xv.size() - 1; j++) {
            if(plain[i][j] == 0) continue;
            ans += (yv[i + 1] - yv[i]) * (xv[j + 1] - xv[j]);
        }
    }
    cout << ans << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}
