NLO

Time limit3sMemory limit512 MB

Summary

Each day a circular UFO zeroes the grass in cells it covers, remaining grass grows by 1 per day; sum all grass after K days.

Level: Medium7 of 10
Topics: Geometry, Prefix sum, Math, Implementation
Solved: No attempts yet

Problem

The locals of the village Žabnik have struggled for many years with unidentified flying objects (UFOs) that create circles in grain fields. The damage is especially noticeable during summer hay mowing.

Consider a rectangular grain field with N rows and M columns. The upper left cell has coordinates (1, 1), and the lower right cell has coordinates (N, M). Each cell grows a certain amount of grass. Initially the amount of grass in every cell is 1. For K days, circular UFOs land on the field and make circles in it. On the morning of the ith day, a UFO of radius Ri centered on the cell with coordinates (Xi, Yi) lands on the field and "mows" all the grass growing on the cells it covers. That is, if (Xi - x)2 + (Yi - y)2 ≤ Ri2, the amount of grass in the cell with coordinates (x, y) becomes 0. Each new day, as the grass grows, the amount of grass in every cell increases by 1.

On the evening of the Kth day, the locals mow all the grass in the grain field that will be stored as cattle feed. How much is the total amount of grass they will store?

Input

The first line contains the positive integers N and M (1 ≤ N, M ≤ 100 000), the dimensions of the grain field.

The second line contains the positive integer K (1 ≤ K ≤ 100), the number of days on which unidentified flying objects land on the grain field before mowing.

In the ith of the following K lines there are three positive integers Xi (1 < Xi < N), Yi (1 < Yi < M), and Ri (1 ≤ Ri ≤ min(Xi - 1, Yi - 1, N - Xi, M - Yi)), which represent the central cell on which the ith UFO lands and the radius of the ith UFO.

Output

Print the total amount of grass that the locals will store after mowing.

Examples3

Example 1
Input
```
6 6
3
4 4 2
3 3 2
2 4 1
```
Expected output
```
68
```
Example 2
Input
```
100 100
2
50 50 49
30 30 29
```
Expected output
```
9534
```

Example 3

Input

33333 44444
1
11111 22222 9999

Expected output

1167355751