The Robot Plow

No attempts yetTime limit1sMemory limit128 MB

Problem

Farmer John has purchased a new robotic plow to relieve himself from the drudgery of plowing field after field after field. The plow does the job, but with one restriction: it can only plow a perfect rectangle whose sides have integer length.

Because FJ's field has trees and other obstacles, he programs the plow to plow many different rectangles, which may overlap. He is curious how many squares of his field are actually plowed after all of the instructions run. Each instruction describes a rectangle by giving the $x$, $y$ coordinates of its lower-left and upper-right corners.

The field is partitioned into squares whose sides are parallel to the $x$ and $y$ axes. The field is $X$ squares wide and $Y$ squares high ($1 \le X \le 240$; $1 \le Y \le 240$). Each of the $I$ instructions ($1 \le I \le 200$) consists of four integers $X_{ll}$, $Y_{ll}$, $X_{ur}$, $Y_{ur}$ ($1 \le X_{ll} \le X_{ur} \le X$; $1 \le Y_{ll} \le Y_{ur} \le Y$), the lower-left and upper-right coordinates of the rectangle to plow. The plow plows every square in the range $(X_{ll} \dots X_{ur},\ Y_{ll} \dots Y_{ur})$, inclusive of both endpoint columns and rows.

Consider a field that is 6 squares wide and 4 squares high. As FJ issues a pair of plowing instructions (shown), the field gets plowed as shown by '*' and '#' (already-plowed squares all look the same, but '#' marks the most recently plowed ones):

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

A total of 14 squares are plowed.

Input

  • Line 1: Three space-separated integers: $X$, $Y$, and $I$
  • Lines 2..I+1: Line $i+1$ contains plowing instruction $i$, described by four integers: $X_{ll}$, $Y_{ll}$, $X_{ur}$, $Y_{ur}$

Output

  • Line 1: A single integer, the total number of squares plowed