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 <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
#include <functional>
#include <stack>
#include <cmath>
#include <cstring>
#include <random>
#include <chrono>
#include <memory>
#include <cassert>
#include <numeric>
#include <iomanip>
#define int long long
#define pic pair<int, char>
#define x first
#define y second
#define ll long long
#define pii pair<long long, long long>
#define endl "\n"
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize ("O3")
#define PI 3.14159265
#define pdd pair<double, double>
#define rect pair<pii, pii>

using namespace std;

const int N = 5e5 + 14;
const int inf = (int)1e9;
const int mod = 1e9 + 7;
const double eps = 1e-6;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

int q;
int n;
vector<rect> v;
int disty[N];
int ysz;
int t[N * 4];
int tag[N * 4];

void compress()
{
	vector<int> ycords;

	for (auto &pp : v)
	{
		ycords.push_back(pp.x.y);
		ycords.push_back(pp.y.y);
	}

	sort(all(ycords));
	ycords.resize(unique(all(ycords)) - ycords.begin());
	ysz = ycords.size();

	map<int, int> mp;

	for (int i = 0; i < ycords.size(); ++i)
	{
		mp[ycords[i]] = i;
		disty[i] = ycords[i] - ycords[0];
	}

	for (auto &pp : v)
	{
		pp.x.y = mp[pp.x.y];
		pp.y.y = mp[pp.y.y];
	}
}

void add(int tl, int tr, int v, int l, int r, int dlt)
{
	if (tl > r || tr < l)
		return;

	if (r < l)
		return;

	if (tl >= l && tr <= r)
	{
		tag[v] += dlt;

		if (tag[v])
			t[v] = disty[tr + 1] - disty[tl];
		else if (tl != tr)
			t[v] = t[v * 2] + t[v * 2 + 1];
		else if (tl == tr)
			t[v] = 0;

		return;
	}

	int mid = (tl + tr) / 2;

	add(tl, mid, v * 2, l, r, dlt);
	add(mid + 1, tr, v * 2 + 1, l, r, dlt);
	t[v] = (tag[v] ? (disty[tr + 1] - disty[tl]) : (t[v * 2] + t[v * 2 + 1]));
}

int get()
{
	return tag[1] ? (disty[ysz - 1] - disty[0]) : (t[2] + t[3]);
}

int solve()
{
	vector<pii> odr;

	for (int i = 0; i < n; ++i)
	{
		odr.emplace_back(i, 0);
		odr.emplace_back(i, 1);
	}

	sort(all(odr), [](pii p1, pii p2) {
	
		int x1 = 0;
		int x2 = 0;

		if (!p1.y)
			x1 = v[p1.x].x.x;
		else
			x1 = v[p1.x].y.x;

		if (!p2.y)
			x2 = v[p2.x].x.x;
		else
			x2 = v[p2.x].y.x;

		if (x1 == x2)
			return p1.y < p2.y;

		return x1 < x2;
	});

	int px = -1;
	ll ans = 0;

	for (auto &pr : odr)
	{
		int curx = 0;
		int up = v[pr.x].y.y;
		int down = v[pr.x].x.y;

		if (!pr.y)
			curx = v[pr.x].x.x;
		else
			curx = v[pr.x].y.x;

		ans += (ll)get() * (ll)(curx - px);

		px = curx;

		if (!pr.y)
			add(0, ysz - 2, 1, down, up - 1, 1);
		else
			add(0, ysz - 2, 1, down, up - 1, -1);
	}

	return ans;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout.precision(20);

	//cin >> q;
	q = 1;

	while (q--)
	{
		cin >> n;

		v.resize(n);

		for (int i = 0; i < n; ++i)
			cin >> v[i].x.x >> v[i].x.y >> v[i].y.x >> v[i].y.y;

		fill(t, t + n * 4 + 10, 0);
		fill(tag, tag + n * 4 + 10, 0);
		ysz = 0;
		fill(disty, disty + n + 10, 0);

		compress();

		cout << solve() << endl;
	}
}

