Posters

Task

In his room, mouse Stofl has a wall on which he has put many posters. Since he is a lazy mouse, he never removes posters, and he sticks new posters over the old ones. So, some posters are overlapping others, but there are still some areas which are not covered. Now, Stofl would like to know how large this uncovered area is.

Input

On the first line of standard input, you are given three integers separated by a single space: $W$, $H$, and $N$, the width and height of the wall, as well as the total number of posters. Each of the following $N$ lines contains four integers separated by a single space, describing one poster: $x_i$ and $y_i$, the horizontal and the vertical distance of the wall's top left corner to the poster's top left corner, followed by $w_i$ and $h_i$, the width and height of the poster.

Output

Output one single integer, the area which is not covered by any poster.

Limits

For every poster, we have $x_i, y_i \geq 0$ and $w_i, h_i > 0$, as well as $x_i+w_i \leq W$ and $y_i+h_i \leq H$.

If your program correctly handles all the cases with $1 \leq W,H,N \leq 200$, you score 70% of the points. For the full score, the limits are $1 \leq W,H \leq 10^9$ and $1 \leq N \leq 500$.

Example 1

InputOutput

8 6 3
1 1 3 2
6 1 2 2
3 2 2 3

33

Example 2

InputOutput

7 6 3
1 2 3 2
3 1 2 4
0 1 6 3

22

Explanation

Below, you see what Stofl's wall looks like in sample test 1 and 2 (character '.' represents empty area, character '#' represents covered area).

........
.###..##
.####.##
...##...
...##...
........
.......
######.
######.
######.
...##..
.......

Submission