题目描述

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$ 天早上设置的禁区中所包含单元格的最小可能数量。

3 3 5 10
3 3 1 1 5
1 3 1 2 7
1 3 3 3 4
1 1 1 2 12
3 3 3 3 6

0
1
1
6
9

9 1 5 1
3 3 1 1 4
5 8 1 1 1
3 5 1 1 3
8 8 1 1 4
8 9 1 1 5

1
6
6
6
7

4596 9794 15 141929907
600 3070 2222 8763 472026497
47 2644 3276 6033 930213777
638 945 304 1100 992702990
370 2211 2178 2977 783902937
277 2601 1559 8989 842013671
566 3272 3124 8456 254633541
91 4241 2655 8035 303526265
1342 3662 3909 7175 685435928
1176 4012 2827 8429 614977118
255 2461 1482 5835 794902067
982 2314 941 3952 342731056
1603 2215 6730 7105 332440107
2301 4568 6898 9561 591652619
124 2097 3520 8882 168525684
1845 3599 5592 7145 555656973

16165282
19783008
25583040
25583040
26266464
28021036
36437770
36437770
36437770
36437770
36437770
36437770
41864676
41864676
41864676

提示

样例 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$ 分）无附加约束条件。