Poster

Aufgabe

Maus Stofl hat in seinem Zimmer eine Wand, an der er viele Poster aufgehängt hat. Da er eine faule Maus ist, entfernt er keine Poster, und klebt die neuen einfach über die alten. Somit hat es nun einige Poster, die andere überlappen, aber es hat auch noch einige Bereiche, die noch unbedeckt sind. Nun möchte Stofl wissen, wie gross diese unbedeckte Fläche genau ist.

Eingabe

Auf der ersten Zeile der Standardeingabe werden dir drei Ganzzahlen gegeben, getrennt durch ein einzelnes Leerzeichen: $W$, $H$, und $N$, die Breite und Höhe der Wand, sowie die totale Anzahl Poster. Jede der darauffolgenden $N$ Zeilen enthält vier Ganzzahlen, getrennt durch ein Leerzeichen, die ein Poster beschreiben: $x_i$ und $y_i$, die horizontale und die vertikale Distanz der Ecke oben links der Wand zur Ecke oben links des Posters, gefolgt von $w_i$ und $h_i$, der Breite und der Höhe des Posters.

Ausgabe

Gib eine einzelne Ganzzahl aus, die Fläche, die von keinem Poster bedeckt ist.

Grenzen

Für jedes Poster gilt $x_i, y_i \geq 0$ und $w_i, h_i > 0$, sowie $x_i+w_i \leq W$ und $y_i+h_i \leq H$.

Wenn dein Programm alle Fälle mit $1 \leq W,H,N \leq 200$ korrekt verarbeitet, erhältst du 70% der Punkte. Für die volle Punktzahl muss dein Programm auch mit $1 \leq W,H \leq 10^9$ und $1 \leq N \leq 500$ umgehen können.

Beispiel 1

InputOutput

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

33

Beispiel 2

InputOutput

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

22

Erklärung

Nachfolgend siehst du, wie Stofls Wand in Beispiel 1 und 2 aussieht (das Zeichen '.' steht für leere Fläche, das Zeichen '#' für bedeckte Fläche).

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

Einsendung