IMBOX - Destroying the Weapon Warehouse

no tags 

Iron man is hovering over enemy territories. He comes across their weapons warehouse. The weapons are stored in N rectangular boxes. No two boxes share edges. Boxes may be located inside other boxes but no two boxes will partially overlap each other. Iron man can destroy a box by sending a magnetic pulse with power equal to area of the box (irrespective of the height of the box). This pulse will destroy anything present inside the box. Since Iron man is running low on power, he conveys the 2-D coordinates of all the boxes (as seen from the top view) to Jarvis(artificial intelligence) to calculate the minimum total power of the pulses that will be used to destroy all the boxes. Help Jarvis in determining the total effective area of the weapon warehouse to which the beam needs to be directed to destroy all the boxes.

Input

The first line of the input contains an integer N denoting the number of rectangular boxes. N lines follow. Each following line contains 4 integers- x_1, y_1, x_2, y_2 where coordinates (x_1,y_1) and (x_2,y_2) uniquely identify a rectangular box.

  • 1N105
  • -108x_1, y_1, x_2, y_2108

Output

Print the total effective area to be destroyed.

Example

Input:
3
0 0 2 2
-1 -1 4 4
5 5 8 8

Output:
34

Explanation

In the given test case, first box lies completely inside the second box so we need not to consider that box in calculating the total effective area. Therefore the answer will simply be the sum of areas of the second and third boxes that is 25+9=34


hide comments
Shivam Gupta: 2017-02-20 22:20:13

for a given x, there will be only one box after overlapping (no multiple boxes in y coordinate)

: 2014-01-04 12:28:59

Last edit: 2014-01-04 12:29:23
super human: 2013-12-27 19:32:55

nice one!

785227: 2013-12-26 15:32:14

@lasagna Answer is 18 :)

Balrog: 2013-12-25 19:30:45

Weak TC's I think.

Pranet Verma: 2013-12-25 17:02:15

some more test cases please? keep getting WA and cant understand why

Last edit: 2013-12-25 17:02:34
785227: 2013-12-24 17:54:13

AC at first attempt :) Nice question

wisfaq: 2013-11-17 06:30:50

Please remove language restrictions


Added by:BLANKRK
Date:2013-11-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013