BUHA

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 100 square bomb-range constraints on an A by B grid, count how many cells satisfy all the inside/outside conditions.

Level: Easy2 of 10
Topics: Array, Simulation, Implementation
Solved: No attempts yet

Problem

Boško and Suško are playing a game on a board of rectangular fields arranged in A rows and B columns.

At the start, Suško secretly places his virtual pillbox on exactly one field of the board. Then Boško throws several virtual bombs, and for each bomb Suško truthfully answers whether his pillbox lies within that bomb's range.

A bomb with (odd) diameter P thrown at field (R, S) has a range that is a square with sides parallel to the board, centered at (R, S), with each side of length P. That is, it covers every field (r, c) with R - (P-1)/2 <= r <= R + (P-1)/2 and S - (P-1)/2 <= c <= S + (P-1)/2 (only the part lying on the board matters).

Given all the bombs and Suško's answers, determine on how many fields the pillbox could be located.

Input

The first line contains three integers A, B and K (1 <= A, B, K <= 100): the number of rows, the number of columns, and the number of bombs thrown.

Each of the next K lines contains four integers R, S, P and T, describing one bomb thrown at row R, column S with diameter P (1 <= P <= 99, P is odd). T is 1 if the pillbox is within that bomb's range, and 0 otherwise.

Output

Print a single integer: the number of fields on which the pillbox could be located.

Examples3

Example 1
Input
```
6 6 2
3 3 3 1
4 4 3 1
```
Expected output
```
4
```
Example 2
Input
```
5 5 3
3 3 3 1
3 4 1 0
3 4 3 1
```
Expected output
```
5
```
Example 3
Input
```
5 4 1
2 1 5 0
```
Expected output
```
8
```