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;

class Point
{
public:
    int x,y;
    Point(int _x=0,int _y=0)
    {
        x=_x;
        y=_y;
    }
};

void compress(vector<Point> &s,vector<Point> &t,vector<int> &posX,vector<int> &posY)
{
    for(int i=0;i<s.size();i++)
    {
        posX.push_back(s[i].x);
        posY.push_back(s[i].y);
    }
    for(int i=0;i<t.size();i++)
    {
        posX.push_back(t[i].x);
        posY.push_back(t[i].y);
    }
    posX.erase(unique(posX.begin(),posX.end()),posX.end());
    posY.erase(unique(posY.begin(),posY.end()),posY.end());
    sort(posX.begin(),posX.end());
    sort(posY.begin(),posY.end());
    for(int i=0;i<s.size();i++)
    {
        s[i].x=lower_bound(posX.begin(),posX.end(),s[i].x)-posX.begin();
        s[i].y=lower_bound(posY.begin(),posY.end(),s[i].y)-posY.begin();
    }
    for(int i=0;i<t.size();i++)
    {
        t[i].x=lower_bound(posX.begin(),posX.end(),t[i].x)-posX.begin();
        t[i].y=lower_bound(posY.begin(),posY.end(),t[i].y)-posY.begin();
    }
}

int main()
{
    int n;
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n)
    {
        int x1,y1,x2,y2;
        vector<Point> s,t;
        for(int i=0;i<n;i++)
        {
            cin>>x1>>y1>>x2>>y2;
            s.push_back(Point(x1,y1));
            t.push_back(Point(x2,y2));
        }
        vector<int> posX,posY;
        compress(s,t,posX,posY);

        vector<vector<bool> > mat(4001,vector<bool>(4001));

        for(int i=0;i<n;i++)
        {
            for(int j=s[i].x;j<t[i].x;j++)
            {
                for(int k=s[i].y;k<t[i].y;k++)
                {
                    mat[j][k]=true;
                }
            }
        }

        ll sum=0;
        for(int i=0;i<posX.size();i++)
        {
            for(int j=0;j<posY.size();j++)
            {
                if(mat[i][j])
                {
                    sum+=1LL*(posX[i+1]-posX[i])*(posY[j+1]-posY[j]);
                }
            }
        }
        cout<<sum<<endl;
    }

    return 0;
}

