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<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
#include<typeinfo>
using namespace std;

const double pi=4*atan(1.0);

constexpr long long mod=static_cast<long long>(1e9+7);

using cWeightEdges=vector<vector<pair<int,int>>>;
using cEdges=vector<vector<int>>;

int main() {
	int N;
	cin>>N;
	vector<array<long long,4>> p(N);
	vector<long long> x(2*N);
	vector<long long> y(2*N);
	set<long long> x_set;
	set<long long> y_set;
	for(auto& val:p){
		cin>>val[0]>>val[1]>>val[2]>>val[3];
		x_set.insert(val[0]);
		x_set.insert(val[2]);
		y_set.insert(val[1]);
		y_set.insert(val[3]);
	}
	for(int i=0;i<N;++i){
		x[i*2]=p[i][0];
		y[i*2]=p[i][1];
		x[i*2+1]=p[i][2];
		y[i*2+1]=p[i][3];
	}
	sort(begin(x),end(x));
	sort(begin(y),end(y));
	auto x_end=unique(begin(x),end(x));
	auto y_end=unique(begin(y),end(y));

	unordered_map<long long,long long> x_Hash;
	unordered_map<long long,long long> y_Hash;
	int cnt=0;
	for(const auto& val:x_set)
		x_Hash.insert(make_pair(val,cnt++));
	cnt=0;
	for(const auto& val:y_set)
		y_Hash.insert(make_pair(val,cnt++));

	for(auto& val:p){
		val[0]=x_Hash[val[0]];
		val[2]=x_Hash[val[2]];
		val[1]=y_Hash[val[1]];
		val[3]=y_Hash[val[3]];
	}

	vector<vector<int>> plane(y_end-begin(y)-1,vector<int>(x_end-begin(x)-1,0));
	for(const auto& val:p){
		for(int i=val[1];i<val[3];++i){
			fill(begin(plane[i])+val[0],begin(plane[i])+val[2],1);
		}
	}

	long long ans=0;
	for(int i=0;i<plane.size();++i){
		for(int j=0;j<plane[i].size();++j){
			if(plane[i][j]==1){
				ans+=(x[j+1]-x[j])*(y[i+1]-y[i]);
			}
		}
	}

	cout<<ans<<endl;

	//system("pause");
	return 0;
}