Cho ma trận N x N toàn 0. Thực hiện Q truy vấn: Cộng V vào hình chữ nhật có góc trên trái (x1, y1) và góc dưới phải (x2, y2). In ra giá trị tại ô (x, y) bất kỳ cuối cùng.

Gợi ý:

D[x1][y1] += V

D[x1][y2+1] -= V

D[x2+1][y1] -= V

D[x2+1][y2+1] += V

Sau đó cộng dồn 2 chiều.

Input:

Dòng 1: N, Q.

Q dòng: x1, y1, x2, y2, V.

Dòng cuối: x, y (tọa độ cần in).

Output:

Giá trị tại A[x][y].

Test Case 1:

Input:

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

Output:

3

(Ô (3,3) thuộc cả 2 hình chữ nhật nên 1+2=3)

Test Case 2:

Input:

5 1
1 1 2 2 10
3 3

Output:

0

Trong một thành phố lưới N × N, có Q trạm phát sóng wifi. Trạm thứ i phủ sóng vùng hình chữ nhật (r1, c1, r2, c2).

Một khu vực được coi là "Vùng Sóng Mạnh" nếu nó được phủ sóng bởi ít nhất K trạm phát khác nhau. Hãy tính diện tích (số lượng ô) của "Vùng Sóng Mạnh".

Input:

• Dòng 1: N, K, Q (1 ≤ N ≤ 1000, 1 ≤ Q ≤ 10^5,1 ≤ K ≤ Q).

• Q dòng tiếp theo: r1, c1, r2, c2 (tương ứng mỗi trạm phát sóng, giá trị phủ mặc định là +1).

Output:

• Một số nguyên duy nhất là số lượng ô thuộc Vùng Sóng Mạnh.

Vi dụ:

Input:

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

Output:

7

Một vùng đất được biểu diễn bởi ma trận N × M ban đầu có độ cao bằng 0. Có Q trận mưa thiên thạch. Trận thứ i làm thay đổi độ cao của vùng đất hình chữ nhật từ góc trái trên (r1, c1) đến góc phải dưới (r2, c2) một lượng là V (nếu V > 0 là đất bồi lên, V < 0 là lún xuống).

Hãy in ra độ cao cuối cùng của vùng đất.

Input:

• Dòng 1: N, M, Q (1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 10^5).

• Q dòng tiếp theo: r1, c1, r2, c2, V (1 ≤ r1 ≤ r2 ≤ N, 1 ≤ cl ≤ c2 ≤ M, |V| ≤ 100).

Output:

• In ra ma trận N x M thể hiện độ cao cuối cùng.

Vi dụ:

Input:

4 4 2
1 1 3 3 1
2 2 4 4 2

Output:

1 1 1 0
1 3 3 2
1 3 3 2
0 2 2 2

Cho ma trận N x M. Thực hiện Q thao tác cộng giá trị V vào vùng hình chữ nhật.

Sau khi thực hiện xong, hãy đếm xem có bao nhiêu ô trong ma trận có giá trị đúng bằng K.

Input:

• Dòng 1: N, M, K, Q (1 <= N, M <= 1000, 1 <= Q <= 10^5, |K| <= 10^9).

• Q dòng tiếp theo: r1, c1, r2, c2, V.

Output:

• Số lượng ô có giá trị bằng K.

Input:

3 3 2 2
1 1 2 2 1
2 2 3 3 1

Output:

1

Tương tự như bài toán trải thảm, nhưng lần này bạn cần tìm diện tích của vùng được phủ bởi ÍT NHẤT K tấm thảm chồng lên nhau.

Input:

• Dòng 1: N, M, K, Q (1 <= N, M <= 2000, 1 <= Q <= 10^5, 1 <= K <= Q).

• Q dòng tiếp theo: r1, c1, r2, c2.

Output:

• Số lượng ô được phủ bởi >= K tấm thảm.

Ví dụ

Input:

4 4 2 2
1 1 3 3
2 2 4 4

Output:

4

Một vương quốc có kích thước N x M. Có Q con quái vật xuất hiện.

Mỗi con quái vật kiểm soát một vùng hình chữ nhật (r1, c1, r2, c2).

Những vùng không bị bất kỳ con quái vật nào kiểm soát được gọi là "Vùng An Toàn".

Hãy đếm số ô thuộc Vùng An Toàn.

Input:

• Dòng 1: N, M, Q (1 <= N, M <= 2000, 1 <= Q <= 10^5).

• Q dòng tiếp theo: r1, c1, r2, c2.

Output:

• Diện tích Vùng An Toàn.

Ví dụ

Input:

5 5 1
2 2 4 4

Output:

16

Một thành phố N x N. Có Q nguồn thải gây ô nhiễm.

Mỗi nguồn thải làm tăng chỉ số ô nhiễm thêm P đơn vị cho vùng (r1, c1, r2, c2).

Tuy nhiên, thành phố cũng có K máy lọc không khí.

Mỗi máy lọc làm GIẢM chỉ số ô nhiễm đi C đơn vị cho vùng (x1, y1, x2, y2).

Tính chỉ số ô nhiễm trung bình của toàn thành phố (tổng ô nhiễm / tổng số ô).

Làm tròn xuống số nguyên gần nhất.

Input:

• Dòng 1: N, Q, K (1 <= N <= 1000, Q, K <= 50000).

• Q dòng tiếp theo: r1, c1, r2, c2, P.

• K dòng tiếp theo: x1, y1, x2, y2, C.

Output:

• Chỉ số ô nhiễm trung bình (số nguyên).

Input:

2 1 1
1 1 2 2 10
1 1 1 1 5

Output:

8

Giải thích: Tổng ô nhiễm là 35. Trung bình 35/4 = 8.75 -> 8.

Sân khấu hình chữ nhật N x M. Có Q đèn chiếu.

Mỗi đèn chiếu vào vùng (r1, c1, r2, c2) với độ sáng S.

Tìm ô có độ sáng lớn nhất và ô có độ sáng nhỏ nhất trên sân khấu.

Input:

• N, M, Q.

• Q dòng: r1, c1, r2, c2, S.

Output:

• Hai số nguyên: Giá trị sáng lớn nhất và giá trị sáng nhỏ nhất.

Ví dụ

Input:

3 3 2
1 1 2 2 10
2 2 3 3 20

Output:

30 0

Cho ma trận N x N.

Thao tác cập nhật (r1, c1, r2, c2, V) chỉ cộng giá trị V vào các ô nằm trên BIÊN của hình chữ nhật đó.

(Các ô bên trong hình chữ nhật không đổi).

Hãy in ra ma trận cuối cùng.

Gợi ý: Cập nhật 4 hình chữ nhật hẹp (2 ngang, 2 dọc) hoặc sử dụng logic trừ vùng bên trong.

Input:

• N, Q.

• Q dòng: r1, c1, r2, c2, V.

Output:

• Ma trận kết quả.

Ví dụ

Input:

3 1
1 1 3 3 5

Output:

5 5 5 
5 0 5 
5 5 5

Cho ma trận N x M bằng 0.

Thực hiện U thao tác cập nhật vùng hình chữ nhật.

Sau đó, thực hiện Q truy vấn. Mỗi truy vấn yêu cầu tính tổng các số trong vùng (x1, y1, x2, y2).

(Lưu ý: Update trước, Query sau).

Gợi ý: Dùng Mảng hiệu để xử lý Update, sau đó dùng Prefix Sum 2D để xử lý Query.

Input:

• N, M, U, Q.

• U dòng cập nhật: r1, c1, r2, c2, V.

• Q dòng truy vấn: x1, y1, x2, y2.

Output:

• Q dòng, mỗi dòng là tổng của vùng được hỏi.

Input:

4 4 1 1
1 1 3 3 1
2 2 4 4

Output:

4

Bản đồ N x M. Mỗi ô có lượng rác ban đầu là A[i][j].

Có Q đội dọn dẹp. Đội thứ i dọn sạch rác (trừ đi lượng rác V) trong vùng (r1, c1, r2, c2).

Nếu lượng rác bị trừ xuống dưới 0 thì coi như bằng 0 (sạch bong).

Hỏi sau cùng tổng lượng rác còn lại trên bản đồ là bao nhiêu?

Input:

• N, M, Q.

• N dòng tiếp theo: Ma trận A ban đầu.

• Q dòng: r1, c1, r2, c2, V.

Output:

• Tổng lượng rác còn lại.

Ví dụ

Input:

2 2 2
10 10
10 10
1 1 1 2 5
1 1 1 1 10

Output:

25