На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.
Входные данные
В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤109, 0≤y1≤y2≤109). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.
Выходные данные
В выходной файл выведите единственное число — ответ на задачу.
| Ввод |
Вывод |
|
3
1 1 3 5
5 2 7 4
2 4 6 7
|
23 |
|
2
0 0 2 2
1 3 2 4
|
5 |