Description

Farmer John bought a new automatic plowing robot to free himself from the daily hard work of plowing. The robot can indeed do the job, but with a small limitation: it can only plow perfect rectangular areas whose side lengths are integers.

Because there are trees and other obstacles scattered around the field, John needs to instruct the robot to plow several different rectangular regions, which may overlap. He is curious how many grid cells will actually be plowed after programming the robot with various instructions (each instruction is described by the lower-left and upper-right $x, y$ coordinates of a rectangle).

As usual, the field is divided into unit grid cells whose edges are parallel to the $x$- and $y$-axes. The whole field is $X$ cells wide and $Y$ cells high ($1 \le X, Y \le 240$). There are $I$ plowing instructions ($1 \le I \le 200$). Each instruction consists of four integers: $Xll, Yll, Xur$ and $Yur$ ($1 \le Xll \le Xur \le X; 1 \le Yll \le Yur \le Y$), representing the coordinates of the lower-left and upper-right corners of the rectangle to be plowed. The robot will plow all grid cells in the rectangle $(Xll \dots Xur, Yll \dots Yur)$—depending on how you interpret it, this might include one more row or column than you initially expect (of course, that depends on your interpretation).

For example, consider a field that is 6 cells wide and 4 cells high. When John issues two plowing instructions (as shown below), the plowed area is indicated by * and # (usually the plowed area looks the same; here # marks the most recently plowed area):

......             **....             #####. 
......  (1,1)(2,4) **....  (1,3)(5,4) #####. 
......             **....             **.... 
......             **....             **....

In the end, 14 cells are plowed.

Score: 25 points.

Input Format

A total of $I+1$ lines.

• The first line contains three space-separated integers: $X, Y$ and $I$.
• Lines 2 through $I+1$: line $i+1$ contains the $i$-th plowing instruction, described by four integers: $Xll, Yll, Xur$ and $Yur$.

Output Format

One line with a single integer, the total number of cells that are plowed.

6 4 2 
1 1 2 4 
1 3 5 4 

14 

Hint

As shown in the example in the statement.

Translated by ChatGPT 5