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 <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 2002;
struct Edge
{
	long long l,r;
	long long h;
	int f;
}e[N<<1];

bool cmp(Edge a,Edge b)
{
	return a.h < b.h;
}
struct Node
{
	int l,r;
	int s;
	long long len;
}q[N*8];
double x[N<<1];
#define ls i<<1
#define rs i<<1|1
#define m(i) ((q[i].l+q[i].r)>>1)
void pushup(int i)
{
	if (q[i].s)
	{
		q[i].len = x[q[i].r+1] - x[q[i].l];
	}
	else if (q[i].l == q[i].r) q[i].len = 0;
	else q[i].len = q[ls].len + q[rs].len;
}
void build(int i,int l,int r)
{
	q[i].l = l,q[i].r = r,q[i].s = 0;q[i].len = 0;
	if (l == r) return ;
	int mid = m(i);
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void update(int i,int l,int r,int f)
{
	if (l == q[i].l &&q[i].r == r)
	{
		q[i].s += f;
		pushup(i);
		return ;
	}
	int mid = m(i);
	if (r <= mid) update(ls,l,r,f);
	else if (l > mid) update(rs,l,r,f);
	else
	{
		update(ls,l,mid,f);
		update(rs,mid+1,r,f);
	}
	pushup(i);
}
int main()
{
    int n;int kas = 0;
    scanf("%d",&n);
    	int tot = 0;
    	for (int i = 1;i <= n;++i,tot+=2)
    	{
    		long long x1,x2;
    		long long y1,y2;
    		scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
    		Edge &t1 = e[tot],&t2 = e[tot+1];
    		t1.l = x1,t1.r = x2,t1.h = y1,t1.f = 1;//上边是1
			t2.l = x1,t2.r = x2,t2.h = y2,t2.f = -1;//下边是-1
			x[tot] = x1,x[tot+1] = x2;
		}
		sort(x,x+tot);sort(e,e+tot,cmp);
		int k = 1;
		//x[0]
		for (int i = 1;i < tot;++i)
		{
			if (x[i]!=x[i-1])
			{
				x[k++] = x[i];
			}
		}
		build (1,0,k-1);//离散后区间是[0,k-1]
		long long ans = 0;
		for (int i = 0;i < tot;++i)
		{
			int l = lower_bound(x,x+k,e[i].l) - x;//找到实际坐标对应的离散坐标
			int r = lower_bound(x,x+k,e[i].r) - x - 1;
			update(1,l,r,e[i].f);
			ans += q[1].len*(e[i+1].h-e[i].h);
		}

    printf("%lld\n",ans);
    return 0;
}
