B - 庭園 3 (Garden 3) 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

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,\ldots ,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.

Input

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

Output

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.

Constraints

  • 1 \leq H \leq 10^9.
  • 1 \leq W \leq 10^9.
  • 1 \leq N \leq 200\,000.
  • 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 5\,000.
  5. (28 points) No additional constraints.

Sample Input 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

Sample Output 1

0
1
1
6
9

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 Input 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

Sample Output 2

1
6
6
6
7

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

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

Sample Output 3

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

This sample input satisfies the constraints of Subtasks 3, 4, and 5.

配点： 100 点

問題文

JOI 庭園は縦 H 行，横 W 列のマス目状に区切られた長方形の形をしている． 上から数えて i 行目，左から数えて j 列目のマスは区画 (i,j) と呼ばれている．

区画に雨が降ることにより，その区画の水分量が増加する． 雨が降る以外に区画の水分量が変化することはない． 水分量が X 以上になった区画はぬかるみになり，危険である． そのため JOI 庭園の管理者である JOI 君は，朝が来るごとに，水分量が X 以上である区画をすべて含むような長方形の立ち入り禁止の領域を 1 つまで設定する． 正確には，4 つの整数 u,d,l,r (1 \leqq u \leqq d \leqq H,1 \leqq l \leqq r \leqq W) を選び，u \leqq i \leqq d と l \leqq j \leqq r を両方満たす区画 (i,j) 全体からなる領域を立ち入り禁止にする．

現在，JOI 庭園のすべての区画の水分量は 0 である． 今日から N 日間，毎日夕方に 1 回ずつ，JOI 庭園に雨が降る． 今日から k-1 日後 (1 \leqq k \leqq N) の夕方には，U_k \leqq i \leqq D_k と L_k \leqq j \leqq R_k を両方満たすような区画 (i,j) に雨が降り， それらの区画の水分量がそれぞれ C_k だけ増加する．

k=1,2,\ldots ,N のそれぞれについて，k 日後の朝に JOI 君が設定する立ち入り禁止の領域に含まれる区画の個数としてありうる最小の値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

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 \leqq k \leqq N) には，k 日後の朝に JOI 君が設定する立ち入り禁止の領域に含まれる区画の個数としてありうる最小の値を出力せよ．

制約

  • 1 \leqq H \leqq 10^9．
  • 1 \leqq W \leqq 10^9．
  • 1 \leqq N \leqq 200\,000．
  • 1 \leqq X \leqq 2\times 10^{14}．
  • 1 \leqq U_k \leqq D_k \leqq H (1 \leqq k \leqq N)．
  • 1 \leqq L_k \leqq R_k \leqq W (1 \leqq k \leqq N)．
  • 1 \leqq C_k \leqq 10^9 (1 \leqq k \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (3 点) X = 1．
  2. (24 点) W = 1．
  3. (15 点) N \leqq 300．
  4. (30 点) N \leqq 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

以下は，各日の水分量の増加と，含まれる区画の個数が最小となるような立ち入り禁止の領域の設定方法の一例である．

  • 0 日後の夕方に，区画 (3,1) の水分量が 5 だけ増加する． 1 日後の朝の時点では，水分量が 10 以上の区画はないため，立ち入り禁止の領域は設定されない．
  • 1 日後の夕方に，区画 (1,1)，(1,2)，(2,1)，(2,2)，(3,1)，(3,2) の水分量がそれぞれ 7 だけ増加する． 2 日後の朝の時点では，水分量が 10 以上の区画は区画 (3,1) である．JOI 君は，u=d=3，l=r=1 を選ぶことにより 1 つの区画を含む立ち入り禁止の領域を設定する．
  • 2 日後の夕方に，区画 (1,3)，(2,3)，(3,3) の水分量がそれぞれ 4 だけ増加する． 3 日後の朝の時点では，水分量が 10 以上の区画は区画 (3,1) である．JOI 君は，u=d=3，l=r=1 を選ぶことにより 1 つの区画を含む立ち入り禁止の領域を設定する．
  • 3 日後の夕方に，区画 (1,1)，(1,2) の水分量がそれぞれ 12 だけ増加する． 4 日後の朝の時点では，水分量が 10 以上の区画は区画 (1,1)，(1,2)，(3,1) である．JOI 君は，u=1，d=3，l=1，r=2 を選ぶことにより 6 つの区画を含む立ち入り禁止の領域を設定する．
  • 4 日後の夕方に，区画 (3,3) の水分量がそれぞれ 6 だけ増加する． 5 日後の朝の時点では，水分量が 10 以上の区画は区画 (1,1)，(1,2)，(3,1)，(3,3) である．JOI 君は，u=1，d=3，l=1，r=3 を選ぶことにより 9 つの区画を含む立ち入り禁止の領域を設定する．

この入力例は小課題 3,4,5 の制約を満たす．

入力例 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

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

出力例 3

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

この入力例は小課題 3,4,5 の制約を満たす．