水星湖（lake）

题目背景

注意：本场比赛提交时不开启文件输入输出。

题目描述

有一个 $n\times m$ 的矩形网格。用数对 $(x, y)$ 表示第 $x$ 行、第 $y$ 列的位置。

网格内有 $q$ 片湖泊（$q$ 可能为 $0$），第 $i$ 片湖泊覆盖了左上角为 $(a_{i, 1}, b_{i, 1})$、右下角为 $(a_{i, 2}, b_{i, 2})$ 的矩形区域，这片区域里的所有位置都被称为湖泊。如果一个位置不属于任何一片湖泊，它就是陆地。湖泊两两不会重叠，但可能相邻。

小 Y 会进行 $r$ 次种树。第 $i$ 次，他在第 $t_i$ 秒向 $(x_i, y_i)$ 里种下一棵树，保证该位置不为湖泊，且要么没有种下或生长过树，要么曾经种下或生长的树已经死亡。保证种树是按照时间顺序进行的，即 $t_1, t_2, \dots, t_r$ 单调不降。

每一秒，对于每个位置 $(x, y)$，若它同时满足如下所有条件，则会在 $(x, y)$ 处生长出一棵树：

• 它是一块无树存活的陆地；
• 它与一块湖泊相邻；
• 它在前一秒与一棵存活的树相邻。

（上述所说的相邻是在四连通意义下的，即位置 $(x_1, y_1)$ 和 $(x_2, y_2)$ 相邻当且仅当 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$。）

如果一棵树在存活大于 $\bm k$ 秒后（以其被种下或生长出来时开始计算），与其相邻的所有位置均为无树存活的陆地，则它会死亡。

小 Y 想要知道：经过充分多时间后（也即，经过足够多的时间，使得网格内不会有新的位置长出树，也不会有旧的树死去的状态下），网格内最终会有多少棵树。

输入格式

第一行，五个整数 $n, m, q, r, k$。

接下来 $q$ 行，每行四个正整数 $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}$，描述第 $i$ 片湖泊的位置。保证湖泊两两不会重叠。

接下来 $r$ 行，每行三个正整数 $t_i, x_i, y_i$，分别表示第 $i$ 棵树被种下的秒数和行列位置。保证 $t_1, t_2, \dots, t_r$ 单调不降。

输出格式

仅一行一个整数，表示经过充分多时间后，网格内最终会有多少棵树。

样例 #1

样例输入 #1

5 6 2 1 1
2 1 3 3
3 5 5 6
1 1 5

样例输出 #1

10

样例 #2

样例输入 #2

3 3 0 3 1
1 3 1
2 1 1
3 2 1

样例输出 #2

2

提示

【样例解释 #1】

如图所示，为经过充分多时间后网格中的情况。

网格内不会有新的位置长出树，也不会有旧的树死去，所以经过充分多时间后，网格内有 $10$ 棵树。

【样例解释 #2】

在这一组数据中，所有位置都是陆地，没有湖泊。

第 $1$ 秒时，第一棵树在 $(3, 1)$ 被种下。

第 $2$ 秒时，第二棵树在 $(1, 1)$ 被种下。紧接着，第一棵树已存活 $> 1$ 秒，且与其相邻的所有位置均为没有存活的树的陆地，因此死亡。

第 $3$ 秒时，第三棵树在 $(2, 1)$ 被种下。紧接着，第二棵树已存活 $> 1$ 秒，而此时第三棵树与其相邻，因此不死亡。

随后，网格内不会有新的位置长出树，也不会有旧的树死去。所以经过充分多时间后，网格内有 $2$ 棵树。

【样例 #3】

见附件中的 lake/lake3.in 与 lake/lake3.ans。

该组样例满足测试点 $4 \sim 7$ 的约束条件。

【样例 #4】

见附件中的 lake/lake4.in 与 lake/lake4.ans。

该组样例满足测试点 $8 \sim 10$ 的约束条件。

【样例 #5】

见附件中的 lake/lake5.in 与 lake/lake5.ans。

该组样例满足测试点 $13 \sim 15$ 的约束条件。

【样例 #6】

见附件中的 lake/lake6.in 与 lake/lake6.ans。

该组样例满足测试点 $16 \sim 20$ 的约束条件。

【数据范围】

本题共 $20$ 个测试点，每个 $5$ 分。

测试点编号	$n,m\le$	$q\le$	$r\le$	$t_i,k\le$
$1\sim3$	$10$
$4\sim7$	$50$	$100$	$1000$
$8\sim 10$	$3000$	$0$	$10^5$	$10^9$
$11\sim12$		$10^5$	$1$
$13\sim15$	$1000$		$10^5$	$12$
$16\sim20$	$3000$			$10^9$

对于全部数据，保证：

• $1 \leq n, m \leq 3000$；
• $0 \leq q \leq 10^5$；
• $1 \leq a_{i, 1} \le a_{i, 2} \leq n$，$1 \leq b_{i, 1} \le b_{i, 2} \leq m$；
• 湖泊两两不会重叠；
• $1 \leq r \leq 10^5$；
• $1 \leq t_1 \leq t_2 \leq \dots \leq t_r \leq 10^9$；
• $1 \leq x_i \leq n$，$1 \leq y_i \leq m$；
• 位置 $(x_i, y_i)$ 不是湖泊且无树存活；
• $1 \leq k \leq 10^9$。

样例下载