P15940 [JOI Final 2026] 花园 3 / Garden 3

JOI 花园是一个矩形，被划分为 $H$ 行 $W$ 列的网格。从上往下数第 $i$ 行、从左往右数第 $j$ 列的单元格被称为单元格 $(i, j)$。 当雨落在一个单元格上时，该单元格的湿度会增加。除了下雨的时候，单元格的湿度永远不会改变。如果一个单元格的湿度达到至少 $X$，该单元格就会变成泥地，这是很危险的。因此，每天早上，JOI 花园的管理员 JOI 君最多可以指定一个矩形的禁区，该禁区包含所有湿度至少为 $X$ 的单元格。更准确地说，JOI 君选择四个整数 $u,d,l,r$（$1 \leq u \leq d \leq H$，$1 \leq l \leq r \leq W$），由所有满足 $u \leq i \leq d$ 和 $l \leq j \leq r$ 的单元格 $(i, j)$ 组成的矩形区域将成为禁区。 初始时，JOI 花园中每个单元格的湿度都为 $0$。 从今天开始，连续 $N$ 天每天傍晚都会下一次雨。在之后的第 $k-1$ 天（$1 \leq k \leq N$）傍晚，雨会落在每一个满足 $U_k \leq i \leq D_k$ 和 $L_k \leq j \leq R_k$ 的单元格 $(i, j)$ 上，每个这样的单元格的湿度会增加 $C_k$。 对于每个 $k=1,2,\dots,N$，编写一个程序计算 JOI 君在之后的第 $k$ 天早上设置的禁区中所包含单元格的最小可能数量。

从标准输入读取以下数据。 > $H$ $W$ $N$ $X$ \ > $U_1$ $D_1$ $L_1$ $R_1$ $C_1$ \ > $U_2$ $D_2$ $L_2$ $R_2$ $C_2$ \ > $\vdots$ \ > $U_N$ $D_N$ $L_N$ $R_N$ $C_N$

向标准输出写入 $N$ 行。输出的第 $k$ 行（$1 \leq k \leq N$）应包含 JOI 君在第 $k$ 天早上设置的禁区中所包含单元格的最小可能数量。

### 样例 1 以下是关于每天湿度如何增加以及如何选择禁区以使包含的单元格数量最小化的一个例子。 - 在第 $0$ 天傍晚，单元格 $(3,1)$ 的湿度增加 $5$。在第 $1$ 天早上，没有湿度至少为 $10$ 的单元格，因此不设置禁区。 - 在第 $1$ 天傍晚，单元格 $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$, $(3,1)$ 和 $(3,2)$ 的湿度各增加 $7$。在第 $2$ 天早上，单元格 $(3,1)$ 的湿度至少为 $10$。JOI君选择 $u = d = 3$ 和 $l = r = 1$，从而设置了一个包含 $1$ 个单元格的禁区。 - 在第 $2$ 天傍晚，单元格 $(1,3)$, $(2,3)$ 和 $(3,3)$ 的湿度各增加 $4$。在第 $3$ 天早上，单元格 $(3,1)$ 的湿度至少为 $10$。JOI君选择 $u = d = 3$ 和 $l = r = 1$，从而设置了一个包含 $1$ 个单元格的禁区。 - 在第 $3$ 天傍晚，单元格 $(1,1)$ 和 $(1,2)$ 的湿度各增加 $12$。在第 $4$ 天早上，单元格 $(1,1)$, $(1,2)$ 和 $(3,1)$ 的湿度至少为 $10$。JOI君选择 $u = 1$, $d = 3$, $l = 1$, $r = 2$，从而设置了一个包含 $6$ 个单元格的禁区。 - 在第 $4$ 天傍晚，单元格 $(3,3)$ 的湿度增加 $6$。在第 $5$ 天早上，单元格 $(1,1)$, $(1,2)$, $(3,1)$ 和 $(3,3)$ 的湿度至少为 $10$。JOI君选择 $u = 1$, $d = 3$, $l = 1$, $r = 3$，从而设置了一个包含 $9$ 个单元格的禁区。 这个样例输入满足子任务 $3,4$ 和 $5$ 的约束条件。 ### 样例 2 这个样例输入满足所有子任务的约束条件。 ### 样例 3 这个样例输入满足子任务 $3,4$ 和 $5$ 的约束条件。 ### 约束条件 - $1 \leq H \leq 10^{9}$。 - $1 \leq W \leq 10^{9}$。 - $1 \leq N \leq 200000$。 - $1 \leq X \leq 2 \times 10^{14}$。 - $1 \leq U_k \leq D_k \leq H$ ($1 \leq k \leq N$)。 - $1 \leq L_k \leq R_k \leq W$ ($1 \leq k \leq N$)。 - $1 \leq C_k \leq 10^{9}$ ($1 \leq k \leq N$)。 - 给定的值均为整数。 ### 子任务 1. （$3$ 分）$X = 1$。 2. （$24$ 分）$W = 1$。 3. （$15$ 分）$N \leq 300$。 4. （$30$ 分）$N \leq 5000$。 5. （$28$ 分）无附加约束条件。