Description

You are given an $N \times M$ rectangular wheat field. Each cell of the field has some amount of grass. Initially, the amount of grass in every cell is $1$.

Over $K$ days, circular UFOs will land on the field and draw circles. On the morning of day $i$, a UFO with radius $R_i$ lands on cell $(X_i, Y_i)$, and all cells within distance $R_i$ from that cell will be affected. If a cell $(x, y)$ is affected, i.e. $(X_i-x)^2+(Y_i-y)^2 \le R_i^2$, then the amount of grass in that cell becomes $0$. When a new day arrives, the amount of grass in every cell increases by $1$.

Find the sum of grass over all cells on the evening of day $K$.

Input Format

The first line contains positive integers $N, M$, representing the size of the field.

The second line contains a positive integer $K$, representing the number of days.

The next $K$ lines each contain positive integers $X_i, Y_i, R_i$, describing the landing cell and the radius of the UFO.

Output Format

Output the total amount of grass.

6 6
3
4 4 2
3 3 2
2 4 1

68

100 100
2
50 50 49
30 30 29

9534

33333 44444
1
11111 22222 9999

1167355751

Hint

Explanation of Sample 1

The field on the evening of day 1:

The field on the evening of day 2:

The field on the evening of day 3:

Therefore, the total amount of grass is $68$ units.

Constraints

For $20\%$ of the testdata, $N, M \le 1000$.

For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le K \le 100$, $1 \lt X_i \lt N$, $1 \lt Y_i \lt M$, $1 \le R_i \le \min(X_i-1, Y_i-1, N-X_i, M-Y_i)$.

Note

The score of this problem follows the original COCI settings, with a full score of $110$.

This problem is translated from COCI2018-2019 CONTEST #3 T4 NLO.

Translated by ChatGPT 5