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<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<queue>
#define null NULL
#define maxn 4000
using namespace std;
struct pNode
{
    int xl,xr,y,type;
};
pNode g[maxn];
int dx[maxn],compress[maxn];

struct Node
{
    int dl,dr,cnt;
    long long s;
    Node *pl,*pr;
};
int n;

void build(Node *&p,int l,int r)
{
    p=(Node *)malloc(sizeof(Node));
    p->dl=l,p->dr=r,p->s=0,p->cnt=0;
    p->pl=null,p->pr=null;
    int mid=(l+r)/2;
    if(r>l)
    {
        build(p->pl,l,mid);
        build(p->pr,mid+1,r);
    }
}

void preorder(Node *p)
{
    if(p!=null)
    {
        printf("%d %d %d %lld\n",p->dl,p->dr,p->cnt,p->s);
        preorder(p->pl);
        preorder(p->pr);
    }
}

void modify(Node *&p)
{
    if(p->cnt>0)
        p->s = compress[p->dr+1]-compress[p->dl];
    else
        p->s=p->pl->s+p->pr->s;
}
void update(Node *&p,int l,int r,int type)
{
    if(p->dl==l &&p->dr==r)
    {
        if(type==0)
        {
            p->cnt += 1;
            p->s = compress[p->dr+1]-compress[p->dl];
        }else
        {
            p->cnt -= 1;
            if(p->cnt==0)
            {
                if(p->dl==p->dr)
                    p->s=0;
                else
                    p->s=p->pl->s+p->pr->s;
            }
        }
        return ;
    }
    int mid=(p->dl+p->dr)/2;
    if(r<=mid)
        update(p->pl,l,r,type);
    else if(l>mid)
        update(p->pr,l,r,type);
    else
        update(p->pl,l,mid,type),update(p->pr,mid+1,r,type);
    if(p->cnt>0)
        p->s = compress[p->dr+1]-compress[p->dl];
    else
        p->s=p->pl->s+p->pr->s;
}

bool cmpy(pNode a,pNode b)
{
    return a.y<b.y;
}
int main()
{
    int i,j,t,x1,y1,x2,y2;
    Node *tree=null;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        dx[2*i]=x1,dx[2*i+1]=x2;///x轴离散化
        g[2*i].xl=x1,g[2*i].xr=x2,g[2*i].y=y1,g[2*i].type=0;///表示矩形的下边线
        g[2*i+1].xl=x1,g[2*i+1].xr=x2,g[2*i+1].y=y2,g[2*i+1].type=1;///表示矩形的上边线
    }
    sort(dx,dx+2*n);
    t=dx[0],i=0,j=0;
    while(i<2*n)
    {
        compress[j++]=t;
        while(dx[i]==t) i++;
        t=dx[i];
    }
    ///compress数组一共num个数字，下标为0~num-1
    int num=j;

    sort(g,g+2*n,cmpy);
    build(tree,0,num-2);
    //preorder(tree);
    long long ans=0;
    for(i=0;i<2*n;i++)
    {
        int xl=lower_bound(compress,compress+num,g[i].xl)-compress;
        int xr=lower_bound(compress,compress+num,g[i].xr)-compress;
        if(i>0)
            ans += (g[i].y-g[i-1].y)*tree->s;
        update(tree,xl,xr-1,g[i].type);
    }
    printf("%lld\n",ans);
    return 0;
}

