NKMARS - Mars Map

(This task was inspired by task ‘Atlantis’ of the Mid–Central European Regional ACM–ICP Contest 2000/2001.)

In the year 2051, several Mars expeditions explored different areas of the red planet and produced maps of these areas. Now, the BaSA (Baltic Space Agency) has an ambitious plan: they would like to produce a map of the whole planet. In order to calculate the necessary effort, they need to know the total size of the area for which maps already exist. It is your task to write a program that calculates this area.

Input

The input starts with a line containing a single integer N (1 ≤ N ≤ 10 000 ), the number of available maps. Each of the following N lines describes a map. Each of these lines contains four integers x1, y1, x2 and y2 (0 ≤ x1 < x2 ≤ 30 000 , 0 ≤ y1 < y2 ≤ 30 000 ). The values ( x1;y1) and ( x2;y2) are the coordinates of, respectively, the bottom-left and the top- right corner of the mapped area. Each map has rectangular shape, and its sides are parallel to the x- and y-axis of the coordinate system.

Output

The output should contain one integer A, the total area of the explored territory (i.e. the area of the union of all the rectangles).

Example

Input
2
10 10 20 20
15 15 25 30

Output
225

Added by:Jimmy
Date:2007-12-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Baltic OI 2001

hide comments
2023-04-23 00:47:53
hv22 is lying
2023-04-23 00:43:21
ac in one go using convex merge sort tree trick with parallel binary search
2018-03-21 19:01:21 Eddy Cael
After several versions, finally, I did it... Good problem :)
2012-07-29 17:54:40 nikoo28
can someone provide me with more test cases??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.