题目描述

给定一个 $N \times M$ 的矩形麦田。麦田的每个区域都生长有一定量的草。所有区域的初始草量均为 $1$。

在 $K$ 天内，圆形的 UFO 将降落在麦田上并画圆。在第 $i$ 天早上，一个半径为 $R_i$ 的 UFO 将降落在区域 $(X_i,Y_i)$，并使得以该区域为圆心，$R_i$ 的半径内的所有区域将会受到影响。如果一个区域 $(x,y)$ 受到影响，且 $(X_i-x)^2+(Y_i-y)^2 \le R_i^2$，则该区域的草量将降为 $0$。在新的一天到来时，每个区域的草量都会增加 $1$。

求在第 $K$ 天晚上，所有区域的草量之和。

输入格式

第一行输入正整数 $N,M$，表示麦地规模。

第二行输入正整数 $K$，表示天数。

接下来的 $K$ 行中的第 $i$ 行，输入正整数 $X_i,Y_i,R_i$，表示降落的区域和 UFO 的半径。

输出格式

输出草的总量。

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

提示

样例 1 解释

第一天晚上的麦田：

$1$
$1$	$1$	$1$	$\red 0$	$1$	$1$
		$\red 0$		$\red 0$
	$\red 0$				$\red 0$
	$1$				$1$
		$1$		$1$

第二天晚上的麦田：

$2$		$\red 0$	$2$
$2$	$\red 0$	$\red 0$	$\red 0$	$2$	$2$
$\red 0$				$\red 0$
$2$				$1$	$1$
	$2$		$1$		$2$
		$2$		$2$

第三天晚上的麦田：

$3$		$1$	$\red 0$	$3$
$3$	$1$	$\red 0$	$\red 0$	$\red 0$	$3$
$1$		$1$		$1$
$3$			$1$	$2$	$2$
	$3$		$2$		$3$
		$3$		$3$

因此总草量为 $68$ 单位。

数据规模与约定

对于 $20\%$ 的数据，$N,M \le 1000$。

对于 $100\%$ 的数据，$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)$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2018-2019 CONTEST #3 T4 NLO。