Задача №3858. 4D: объединение прямоугольников

На плоскости задано \(N\) прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.

Входные данные

В первой строке входного файла указано число \(N\) \((0 \le N \le 1500)\). В следующих \(N\) строках заданы по 4 целых числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего \((0 \le x_1 \le x_2 \le 10^9,\, 0 \le y_1 \le y_2 \le 10^9)\). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

Выходные данные

В выходной файл выведите единственное число — ответ на задачу.

Примеры
Входные данные
3
1 1 3 5
5 2 7 4
2 4 6 7
Выходные данные
23
Входные данные
2
0 0 2 2
1 3 2 4
Выходные данные
5
Сдать: для сдачи задач необходимо войти в систему