Problem G
Gameworld Tornado
The Brilliant Game Overseers (BGO) is building a brand new game. The investors have noted that large gameworlds is a selling point these days, so in order to appease the them, a large gameworld with lots of interesting activities has been planned. In addition to a large map showing the entire world in all its glory, a number of smaller maps in various dimensions have been designed showing the layout of smaller features in the Game. Because features should be spread out a little, these maps can overlap.
Woe upon woe, the day after all maps had finally been finished, a tornado blew through the offices of BGO, and now the master map has been lost, as well as a number of the smaller maps. Desperate to salvage as much as possible of the Game, you have been tasked with trying to piece together as much as possible of the original map, using the feature maps that were left behind by the tornado. Luckily all the maps have their coordinates marked and are axis aligned, so you figure a good start will be to find out how large is the area (in pixels) covered by the remaining maps.
Input
The input starts with an integer $n$ ($1 \leq n \leq 100\, 000$) denoting the number of axis aligned rectangular maps you have left. Then follows $n$ lines representing the maps, each with four integers $x_1, y_1, x_2, y_2$ where $0 \leq x_1, y_1, x_2, y_2 \leq 10^9$. $x_1$ and $y_1$ are the coordinates of the lower left corner of the rectangle, and $x_2$ and $y_2$ are the upper right corner of the rectangle, i.e. $x_1 < x_2$ and $y_1 < y_2$.
Output
The total area of the game world covered by the remaining maps.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 2 4 4 3 3 5 5 |
7 |
