Buildings

A building company needs to create a software to analyze a bidimensional plane, that contains the top view of a construction.

Every building that is constructed at the bottom has a height of $1$ , and the company allows to build one, two, more or no buildings above one building, such that the height of these buildings will increase by $1$ , and the horizontal and vertical coordinates of these buildings will always fit in the coordinates of the building that is down, so the area will also be smaller.

This file and this file contain the following: in the first line there is a number $n$ that represents the number of buildings, then there are $n$ lines that represent the coordinates of every building with the following structure:

$x_1 \quad y_1 \quad x_2 \quad y_2$

Where $(x_1,y_1)$ is the upper left coordinate of the building, and $(x_2,y_2)$ is the lower right coordinate of the building, and $0 \leq x_1,y_1,x_2,y_2 \leq 65535$ .

Your program must compute the total volume for the input given. If the volume for the first file is $a$ and the volume for the second file is $b$ , give your answer as $(a+b) \mod (2^{16}+1)$ .

For example, consider the following input:

$5 \\ 60 \quad 25 \quad 85 \quad 45\\ 20 \quad 15 \quad 45 \quad 40\\ 10 \quad 5 \quad 100 \quad 50\\ 30 \quad 20 \quad 35 \quad 35\\ 40 \quad 30 \quad 42 \quad 38$

The plane would be the following (note that the coordinates can be given in any order):

Then, the area for the buildings will be:

$[A]=(100-10)(50-5)=4050 \\ [B]=(45-20)(40-15)=625 \\ [C]=(85-60)(45-25)=500 \\ [D]=(35-30)(35-20)=75 \\ [E]=(42-40)(38-30)=16$

Now, $D$ and $E$ are above $B$ and $B$ is above $A$ , so the height of $D$ and $E$ is $3$ , and the height of $B$ is $2$ ; and $C$ is above $A$ , so the height of $C$ is $2$ and, of course, the height of $A$ is $1$ . So, the volume would be:

$V=3[D]+3[E]+2[B]+2[C]+[A]\\V=3(75)+3(16)+2(625)+2(500)+4050=6573$ .