JOI-Garden 的形状为矩形，被划分为 $H$ 行 $W$ 列的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的单元格称为单元格 $(i, j)$。

当雨水落在某个单元格上时，该单元格的湿度会增加。单元格的湿度只会在下雨时发生变化。如果某个单元格的湿度达到 $X$ 或以上，该单元格就会变成泥泞，这是危险的。因此，每天早上，JOI-Garden 的管理者 JOI-kun 可以指定至多一个包含所有湿度达到 $X$ 或以上单元格的矩形禁区。更具体地说，JOI-kun 选择四个整数 $u, d, l, r$ ($1 \le u \le d \le H, 1 \le l \le r \le W$)，则满足 $u \le i \le d$ 且 $l \le j \le r$ 的所有单元格 $(i, j)$ 构成的矩形区域变为禁区。

最初，JOI-Garden 中每个单元格的湿度均为 0。

从今天开始，未来 $N$ 天内，每天傍晚都会下一次雨。在第 $k$ 天傍晚（$1 \le k \le N$），雨水落在所有满足 $U_k \le i \le D_k$ 且 $L_k \le j \le R_k$ 的单元格 $(i, j)$ 上，这些单元格的湿度各增加 $C_k$。

对于每个 $k = 1, 2, \dots, N$，请编写一个程序，计算 JOI-kun 在第 $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 \le k \le N$）应包含 JOI-kun 在第 $k$ 天早上设置的禁区所包含的单元格数量的最小值。

数据范围

• $1 \le H \le 10^9$
• $1 \le W \le 10^9$
• $1 \le N \le 200\,000$
• $1 \le X \le 2 \times 10^{14}$
• $1 \le U_k \le D_k \le H$ ($1 \le k \le N$)
• $1 \le L_k \le R_k \le W$ ($1 \le k \le N$)
• $1 \le C_k \le 10^9$ ($1 \le k \le N$)
• 给定值均为整数。

子任务

1. (3 分) $X = 1$。
2. (24 分) $W = 1$。
3. (15 分) $N \le 300$。
4. (30 分) $N \le 5\,000$。
5. (28 分) 无附加限制。

样例

输入格式 1

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

输出格式 1

0
1
1
6
9

说明

以下是湿度每天如何增加以及如何选择禁区以使包含的单元格数量最小化的一个示例：

• 第 1 天早上（第 0 天傍晚后），单元格 $(3, 1)$ 的湿度增加 5。没有单元格的湿度达到 10，因此不设置禁区。
• 第 2 天早上（第 1 天傍晚后），单元格 $(1, 1), (1, 2), (2, 1), (2, 2), (3, 1)$ 和 $(3, 2)$ 的湿度各增加 7。单元格 $(3, 1)$ 的湿度达到 10 或以上。JOI-kun 选择 $u = d = 3$ 且 $l = r = 1$，从而设置了一个包含 1 个单元格的禁区。
• 第 3 天早上（第 2 天傍晚后），单元格 $(1, 3), (2, 3)$ 和 $(3, 3)$ 的湿度各增加 4。单元格 $(3, 1)$ 的湿度达到 10 或以上。JOI-kun 选择 $u = d = 3$ 且 $l = r = 1$，从而设置了一个包含 1 个单元格的禁区。
• 第 4 天早上（第 3 天傍晚后），单元格 $(1, 1)$ 和 $(1, 2)$ 的湿度各增加 12。单元格 $(1, 1), (1, 2)$ 和 $(3, 1)$ 的湿度达到 10 或以上。JOI-kun 选择 $u = 1, d = 3, l = 1, r = 2$，从而设置了一个包含 6 个单元格的禁区。
• 第 5 天早上（第 4 天傍晚后），单元格 $(3, 3)$ 的湿度增加 6。单元格 $(1, 1), (1, 2), (3, 1)$ 和 $(3, 3)$ 的湿度达到 10 或以上。JOI-kun 选择 $u = 1, d = 3, l = 1, r = 3$，从而设置了一个包含 9 个单元格的禁区。

输入格式 2

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

输出格式 2

1
6
6
6
7

输入格式 3

5 5 4 10
1 5 1 5 2
1 5 1 5 3
1 5 1 5 4
1 5 1 5 5

输出格式 3

0
0
0
25