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 <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n; cin >> n;
    vector<ll> x,y;
    vector<ll> x1in(n),y1in(n),x2in(n),y2in(n);
    rep(i,n){
        cin >> x1in[i] >> y1in[i] >> x2in[i] >> y2in[i];
        x.pb(x1in[i]); x.pb(x2in[i]);
        y.pb(y1in[i]); y.pb(y2in[i]);
    }
    sort(ALL(x)); sort(ALL(y));
    x.erase(unique(ALL(x)),x.end());
    y.erase(unique(ALL(y)),y.end());
    vector<ll> low[4040],high[4040];
    rep(i,n){
        x1in[i]=(int)(lower_bound(ALL(x),x1in[i])-x.begin());
        x2in[i]=(int)(lower_bound(ALL(x),x2in[i])-x.begin());
        y1in[i]=(int)(lower_bound(ALL(y),y1in[i])-y.begin());
        y2in[i]=(int)(lower_bound(ALL(y),y2in[i])-y.begin());
        low[y1in[i]].pb(x1in[i]);
        low[y1in[i]].pb(x2in[i]);
        high[y2in[i]].pb(x1in[i]);
        high[y2in[i]].pb(x2in[i]);
    }
    ll ans=0;
    vector<ll> imos(4040,0);
    rep(i,y.size()-1){
        for(int j=0;j<low[i].size();j+=2){
            for(int k=low[i][j];k<low[i][j+1];k++){
                imos[k]--;
            }
        }
        for(int j=0;j<high[i].size();j+=2){
            for(int k=high[i][j];k<high[i][j+1];k++){
                imos[k]++;
            }
        }
        rep(j,x.size()-1){
            if(imos[j]!=0){
                ans+=(y[i+1]-y[i])*(x[j+1]-x[j]);
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

