P15940 Garden 3

The JOI-Garden has a rectangular shape divided into a grid of $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i, j)$. When rain falls on a cell, the moisture level of that cell increases. The moisture level of a cell never changes except when it rains. If the moisture level of a cell becomes at least $X$, the cell turns into mud, which is dangerous. Therefore, every morning, JOI-kun, the manager of the JOI-Garden, may designate at most one rectangular off-limits area that contains all cells whose moisture level is at least $X$. More precisely, JOI-kun chooses four integers $u,d,l,r$ ($1 \leq u \leq d \leq H$, $1 \leq l \leq r \leq W$), and the rectangular region consisting of all cells $(i, j)$ satisfying $u \leq i \leq d$ and $l \leq j \leq r$ becomes off-limits. Initially, the moisture level of every cell in the JOI Garden is $0$. Starting today, it will rain once every evening for $N$ days. On the evening of the $(k-1)$-th day after ($1 \leq k \leq N$), rain falls on every cell $(i, j)$ satisfying $U_k \leq i \leq D_k$ and $L_k \leq j \leq R_k$, and the moisture level of each such cell increases by $C_k$. For each $k=1,2,\dots,N$, write a program that computes the minimum possible number of cells contained in the off-limits area that JOI-kun sets on the morning of the $k$-th day after.

Read the following data from the standard input. > $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$

Write $N$ lines to the standard output. The $k$-th line ($1 \leq k \leq N$) of the output should contain the minimum possible number of cells contained in the off-limits area that JOI-kun sets on the morning of day $k$.

### Sample 1 The following is one example of how the moisture levels increase each day and how the off-limits area can be chosen so that the number of contained cells is minimized. - On the evening of day $0$, the moisture level of cell $(3,1)$ increases by $5$. On the morning of day $1$, there are no cells whose moisture level of at least $10$, so no off-limits area is set. - On the evening of day $1$, the moisture level of cells $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$, $(3,1)$, and $(3,2)$ each increase by $7$. On the morning of day $2$, cell $(3,1)$ has moisture level of at least $10$. JOI-kun chooses $u = d = 3$ and $l = r = 1$, thereby setting a off-limits area that contains $1$ cell. - On the evening of day $2$, the moisture level of cells $(1,3)$, $(2,3)$, and $(3,3)$ each increase by $4$. On the morning of day $3$, cell $(3,1)$ has moisture level of at least $10$. JOI-kun chooses $u = d = 3$ and $l = r = 1$, thereby setting a off-limits area that contains $1$ cell. - On the evening of day $3$, the moisture level of cells $(1,1)$, and $(1,2)$ each increase by $12$. On the morning of day $4$, cells $(1,1)$,$(1,2)$, and $(3,1)$ has moisture level of at least $10$. JOI-kun chooses $u = 1$, $d = 3$, $l = 1$, $r = 2$, thereby setting a off-limits area that contains $6$ cells. - On the evening of day $4$, the moisture level of cell $(3,3)$ increases by $6$. On the morning of day $5$, cells $(1,1)$, $(1,2)$, $(3,1)$, and $(3,3)$ has moisture level of at least $10$. JOI-kun chooses $u = 1$, $d = 3$, $l = 1$, $r = 3$, thereby setting a off-limits area that contains $9$ cells. This sample input satisfies the constraints of Subtasks $3,4$, and $5$. ### Sample 2 This sample input satisfies the constraints of all the subtasks. ### Sample 3 This sample input satisfies the constraints of Subtasks $3,4$, and $5$. ### Constraints - $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$). - Given values are all integers. ### Subtasks 1. ($3$ points) $X = 1$. 2. ($24$ points) $W = 1$. 3. ($15$ points) $N \leq 300$. 4. ($30$ points) $N \leq 5000$. 5. ($28$ points) No additional constraints.