AT_joi2026final_b 庭園 3 (Garden 3)

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. ( $ 3 $ 点) $ X = 1 $ ． 2. ( $ 24 $ 点) $ W = 1 $ ． 3. ( $ 15 $ 点) $ N \leqq 300 $ ． 4. ( $ 30 $ 点) $ N \leqq 5\,000 $ ． 5. ( $ 28 $ 点) 追加の制約はない． --- ### Sample Explanation 1 以下は，各日の水分量の増加と，含まれる区画の個数が最小となるような立ち入り禁止の領域の設定方法の一例である． - $ 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 $ の制約を満たす． --- ### Sample Explanation 2 この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 3,4,5 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．