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>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

struct lect
{
    int xs, xe, ys, ye;
};

int main()
{
    int n;
    cin >> n;
    vector<lect> lects(n);
    rep(i, n)
    {
        cin >> lects[i].xs >> lects[i].ys >> lects[i].xe >> lects[i].ye;
    }
    vector<long long int> largeX;
    vector<long long int> largeY;
    rep(i, lects.size())
    {
        largeX.push_back(lects[i].xs);
        largeX.push_back(lects[i].xe);
        largeY.push_back(lects[i].ys);
        largeY.push_back(lects[i].ye);
    }
    SORT(largeX);
    SORT(largeY);
    largeX.erase(std::unique(largeX.begin(), largeX.end()), largeX.end());
    largeY.erase(std::unique(largeY.begin(), largeY.end()), largeY.end());
    map<long long int, long long int> compX;
    map<long long int, long long int> compY;
    map<long long int, long long int> invCompX;
    map<long long int, long long int> invCompY;
    rep(i, largeX.size())
    {
        compX[largeX[i]] = i;
        invCompX[i] = largeX[i];
    }
    rep(i, largeY.size())
    {
        compY[largeY[i]] = i;
        invCompY[i] = largeY[i];
    }
    int compArea[largeX.size() + 2][largeY.size() + 2];

    rep(x, largeX.size() + 2)
    {
        rep(y, largeY.size() + 2)
        {
            compArea[x][y] = 0;
        }
    }

    for (auto lec : lects)
    {
        compArea[compX[lec.xs] + 1][compY[lec.ys] + 1] += 1;
        compArea[compX[lec.xe] + 1][compY[lec.ys] + 1] -= 1;
        compArea[compX[lec.xs] + 1][compY[lec.ye] + 1] -= 1;
        compArea[compX[lec.xe] + 1][compY[lec.ye] + 1] += 1;
    }
    //make imos

    rep(x, largeX.size() + 2)
    {
        REP(y, 1, largeY.size() + 2)
        {
            compArea[x][y] += compArea[x][y - 1];
        }
    }
    REP(x, 1, largeX.size() + 2)
    {
        rep(y, largeY.size() + 2)
        {
            compArea[x][y] += compArea[x - 1][y];
        }
    }


    long long int ans = 0;
    REP(x, 1, largeX.size() + 1)
    {
        REP(y, 1, largeY.size() + 1)
        {
            if (compArea[x][y] == 0)
                continue;
            else
                ans += abs(invCompX[x] - invCompX[x - 1]) * abs(invCompY[y] - invCompY[y - 1]);
            if (compArea[x][y] > 1)
            {
                compArea[x][y] = 0;
            }
        }
    }


    cout << ans << endl;
    return 0;
}
