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 <algorithm>
#include <cstdio>
#include <utility>
#include <vector>

using namespace std;

#define int long long
#define dotimes(i, n) for (int i = 0, i##max__ = (n); i < i##max__; i++)
#define whole(x, f, ...) ([&](decltype((x)) c) { return (f)(begin(c), end(c), ## __VA_ARGS__); })(x)

int rint() {
  int x;
  scanf("%lld", &x);
  return x;
}

void wint(int x) {
  printf("%lld\n", x);
}

template<typename T> int size(T const& c) { return static_cast<int>(c.size()); }
template <typename T> bool maxs(T& a, T const& b) { return a < b ? a = b, true : false; }
template <typename T> bool mins(T& a, T const& b) { return a > b ? a = b, true : false; }

signed main() {
  const int N = rint();
  vector<pair<int, int>> cxs, cys;
  cxs.reserve(2*N);
  cys.reserve(2*N);
  dotimes(i, N) {
    cxs.emplace_back(rint(), 2*i);
    cys.emplace_back(rint(), 2*i);
    cxs.emplace_back(rint(), 2*i+1);
    cys.emplace_back(rint(), 2*i+1);
  }
  // compress
  auto second_lt = [](pair<int, int> p1, pair<int, int> p2) { return p1.second < p2.second; };
  whole(cxs, sort);
  vector<int> xs;
  xs.emplace_back(cxs[0].first);
  dotimes(i, 2*N) {
    if (xs.back() != cxs[i].first)
      xs.emplace_back(cxs[i].first);
    cxs[i].first = ::size(xs)-1;
  }
  whole(cxs, sort, second_lt);
  whole(cys, sort);
  vector<int> ys;
  ys.emplace_back(cys[0].first);
  dotimes(i, 2*N) {
    if (ys.back() != cys[i].first)
      ys.emplace_back(cys[i].first);
    cys[i].first = ::size(ys)-1;
  }
  whole(cys, sort, second_lt);
  // imoz
  vector<vector<int>> board(ys.size(), vector<int>(xs.size()));
  dotimes(i, N) {
    board[cys[2*i].first][cxs[2*i].first]++;
    board[cys[2*i].first][cxs[2*i+1].first]--;
    board[cys[2*i+1].first][cxs[2*i].first]--;
    board[cys[2*i+1].first][cxs[2*i+1].first]++;
  }
  dotimes(j, ys.size()) dotimes(i, xs.size()-1) board[j][i+1] += board[j][i];
  dotimes(i, xs.size()) dotimes(j, ys.size()-1) board[j+1][i] += board[j][i];
  int r = 0;
  dotimes(j, ys.size()-1) dotimes(i, xs.size()-1) if (board[j][i]) r += (ys[j+1] - ys[j]) * (xs[i+1] - xs[i]);
  wint(r);
  return 0;
}

