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 <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template<typename T>
struct Compress{
    vector<T> xs;
    Compress() = default;
    Compress(const vector<T> &vs){
        add(vs);
    }
    Compress(const initializer_list<vector<T>> &vs){
        for(auto &p : vs)   add(p);
    }

    // vs 内の座標をすべて追加
    void add(const vector<T> &vs){
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x){
        xs.emplace_back(x);
    }
    
    void build(){
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    // vs 内の座標を座標圧縮したものを返す
    vector<int> get(const vector<T> &vs) const{
        vector<int> ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x){
            return lower_bound(begin(xs), end(xs), x) - begin(xs);
        });
        return ret;
    }

    // 座標 x を座標圧縮したものを返す (x が xs 内で何番目にあるかを返す)
    int get(const T &x) const{
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    // 座標圧縮後の k が示す実際の座標を返す
    const T &operator[](int k) const{
        return xs[k];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> sx(N), sy(N), tx(N), ty(N);
    Compress<int> xs, ys;
    for(int i = 0; i < N; ++i){
        cin >> sx[i] >> sy[i] >> tx[i] >> ty[i];
        xs.add(sx[i]), xs.add(tx[i]);
        ys.add(sy[i]), ys.add(ty[i]);
    }
    xs.build(), ys.build();

    int H = xs.xs.size(), W = ys.xs.size();
    vector<vector<int>> S(H + 5, vector<int>(W + 5, 0));
    for(int i = 0; i < N; ++i){
        int ly = ys.get(sy[i]), ry = ys.get(ty[i]);
        for(int j = xs.get(sx[i]); j < xs.get(tx[i]); ++j){
            ++S[j][ly];
            --S[j][ry];
        }
    }
    for(int i = 0; i < H; ++i){
        for(int j = 0; j < W; ++j){
            S[i][j + 1] += S[i][j];
        }
    }

    ll ans = 0;
    for(int i = 0; i < H; ++i){
        for(int j = 0; j < W; ++j){
            if(!S[i][j])    continue;
            ans += (ll)(xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]);
        }
    }
    cout << ans << endl;
}
