Vườn JOI là lưới hình chữ nhật có \(H\) hàng và \(W\) cột. Ô ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang phải được gọi là \((i,j)\). Ban đầu, lượng nước của mọi ô bằng \(0\) và chỉ tăng khi có mưa.

Trong \(N\) ngày liên tiếp, vào buổi tối ngày \(k-1\) (\(1 \le k \le N\)), mọi ô \((i,j)\) thỏa \(U_k\le i\le D_k\) và \(L_k\le j\le R_k\) tăng lượng nước thêm \(C_k\). Khi lượng nước của một ô đạt ít nhất \(X\), ô đó trở thành bùn lầy và gây nguy hiểm.

Vì vậy, vào mỗi buổi sáng, JOI-kun, người quản lý vườn JOI, được lập nhiều nhất một khu vực cấm hình chữ nhật bao phủ tất cả các ô nguy hiểm. Nếu không có ô nguy hiểm, JOI-kun có thể không lập khu vực cấm nào; khi đó số ô bị cấm là \(0\). Với từng \(k\), hãy tìm diện tích nhỏ nhất có thể của khu vực cấm vào buổi sáng ngày \(k\).

Cụ thể, nếu lập khu vực cấm, JOI-kun chọn bốn số nguyên \(u,d,l,r\) với \(1 \le u \le d \le H\) và \(1 \le l \le r \le W\); khu vực cấm gồm các ô \((i,j)\) thỏa \(u \le i \le d\), \(l \le j \le r\). Diện tích ở đây là số ô thuộc khu vực cấm.

Dữ liệu vào

Dòng đầu gồm \(H,W,N,X\). \(N\) dòng tiếp theo, dòng \(k\) gồm \(U_k,D_k,L_k,R_k,C_k\).

Dữ liệu ra

In \(N\) dòng. Dòng \(k\) là diện tích nhỏ nhất của khu vực cấm vào buổi sáng ngày \(k\).

Ràng buộc

• \(1\le H,W\le10^9\).
• \(1\le N\le200000\).
• \(1\le X\le2\times10^{14}\).
• \(1\le U_k\le D_k\le H\).
• \(1\le L_k\le R_k\le W\).
• \(1\le C_k\le10^9\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(3\) điểm: \(X=1\).
2. \(24\) điểm: \(W=1\).
3. \(15\) điểm: \(N\le300\).
4. \(30\) điểm: \(N\le5000\).
5. \(28\) điểm: không có ràng buộc thêm.

Ví dụ

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

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 1, bài Garden 3, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.