Description

Suppose that there are N rectangles. Each side of the rectangle is parallel to the x-axis and the y-axis. Each rectangle has the left bottom coordinate (x1, y1) and the right top coordinate (x2, y2), which is represented as (x1, y1, x2, y2). Each rectangle can be overlapped with each other. You want to know the size occupied by the rectangles. The following is an example when N=5.

직사각형1_n91auy.png

In the above figure, 5 rectangles (1, 1, 6, 5), (2, 0, 4, 2), (2, 4, 5, 7), (4, 3, 8, 6), (7, 5, 9, 7) are placed. The size covered by all the rectangles is the same size within the black border.

직사각형2_sfgsce.png

In the above example, the size covered by the 5 rectangles is 38.

Given the coordinates of rectangles on the plane rectangles as a parameter, write a function solution to return the size covered by the rectangles.

Constraints
  • The number of rectangles N : 1 ≤ N ≤ 100,000
  • The coordinates or rectangles : x1, y1, x2, y2 : 0 ≤ x1 < x2 ≤ 109 , 0 ≤ y1 < y2 ≤ 109
  • x1, y1, x2, y2 are integer number.

Examples
rectangles result
[[0, 1, 4, 4], [3, 1, 5, 3]] 14
[[1, 1, 6, 5], [2, 0, 4, 2], [2, 4, 5, 7], [4, 3, 8, 6], [7, 5, 9, 7]] 38

Example #1
The size occupied by the rectangle (0, 1, 4, 4) and (3, 1, 5, 3) are 12 and 4, respectively. Since the size overlapped by 2 rectangles is 2, total size is 12 + 4 - 2 = 14.

Example #2
This is the same with an example in problem statement.

Result Stop
Result of [Run] or [Submit] will be displayed here