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 <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <fstream>
#include <bitset>
#include <time.h>
#include <assert.h>

#define LL long long
#define VI vector<int>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

using namespace std;


class Compress {
public:
    vector<long long> v;
    map<long long, long long> rev;
    
    // ??§?¨???§?????????
    // vec????????¨????????±??????????????????????????????????????????????´???????????????????
    Compress(vector<long long> vec) {
        this->v = vec;
        sort(this->v.begin(), this->v.end());
        this->v.erase(unique(this->v.begin(), this->v.end()), this->v.end());
        
        for (long long x : v) {
            rev[this->zip(x)] = x;
        }
    }

    long long zip(long long x) {
        return lower_bound(ALL(this->v), x) - this->v.begin();
    }

    long long unzip(long long x) {
        return this->rev[x];
    }
};


int main(int argc, char *argv[]) {
    LL N, X1, Y1, X2, Y2;
    
    cin >> N;
    vector<LL> allX(N), allY(N);
    vector<LL> x1(N), y1(N), x2(N), y2(N);
    FOR(i, 0, N) {
        cin >> X1 >> Y1 >> X2 >> Y2;
        x1[i] = X1;
        y1[i] = Y1;
        x2[i] = X2;
        y2[i] = Y2;
        
        allX.push_back(X1);
        allX.push_back(X2);
        allY.push_back(Y1);
        allY.push_back(Y2);
    
    }
    allX.push_back(1000000001);
    allY.push_back(1000000001);
    
    // ??§?¨???§???
    Compress cx(allX);
    Compress cy(allY);
    
    
    vector<vector<int>> field(5100, vector<int>(5100, 0));
    FOR(i, 0, N) {
        field[cy.zip(y1[i])][cx.zip(x1[i])]++;
        field[cy.zip(y2[i])][cx.zip(x2[i])]++;
        field[cy.zip(y1[i])][cx.zip(x2[i])]--;
        field[cy.zip(y2[i])][cx.zip(x1[i])]--;
    }
    
    // ?´???????
    FOR(y, 0, field.size() - 1) {
        FOR(x, 1, field[0].size() - 1) {
            field[y][x] += field[y][x-1];
        }
    }
    FOR(x, 0, field[0].size()) {
        FOR(y, 1, field.size()) {
            field[y][x] += field[y-1][x];
        }
    }
    
    LL area = 0;
    FOR(y, 0, field.size() - 1) {
        FOR(x, 0, field[0].size() - 1) {
            if (field[y][x]) {
                area += (cx.unzip(x + 1) - cx.unzip(x)) * (cy.unzip(y + 1) - cy.unzip(y));
            }
        }
    }

    cout << area << endl;
}