Mảng A ban đầu toàn 0. Sau nhiều lần cập nhật mảng A từ L đến R lên V đơn vị hãy kiểm tra xem mảng A có tạo thành dạng "Đỉnh núi" hay không. (Mảng tạo thành đỉnh núi khi mảng tăng dần đến một vị trí k rồi giảm dần). In "YES" hoặc "NO".

Input:

Dòng 1: N, Q.

Q dòng tiếp theo: L, R, V (V luôn dương).

Ràng Buộc (Constraints):

Thời gian giới hạn (Time Limit): 1 giây.

Bộ nhớ giới hạn (Memory Limit): 256 MB.

N (Số phần tử mảng): 1 <= N <= 10^6.

Q (Số truy vấn): 1 <= Q <= 10^5.

L, R: 1 <= L < R <= N.

V (Giá trị cộng thêm): 1 <= V <= 10^9.

Test Case 1:

Input:

3 2
1 3 1
2 2 1

Output:

YES

Giải thích:

Ban đầu: 0 0 0

Cập nhật 1 3 1 (Cộng 1 vào từ 1 đến 3): Mảng thành 1 1 1.

Cập nhật 2 2 1 (Cộng 1 vào từ 2 đến 2): Mảng thành 1 2 1.

Kiểm tra: Tăng 1->2, Giảm 2->1. Đây là đỉnh núi.

Test Case 2:

Input:

5 2
1 2 5
4 5 5

Output:

NO

(Mảng: 5 5 0 5 5 -> Thung lũng, không phải núi)

Cho một ma trận số nguyên A có kích thước M × N (gồm M hàng và N cột). Các hàng được đánh số từ 1 đến M, các cột được đánh số từ 1 đến N.

Có Q truy vấn. Mỗi truy vấn cung cấp một tọa độ giao điểm (r, c) nằm trong ma trận (1 ≤ r < M, 1 ≤ c < N). Điểm giao cắt này sẽ chia ma trận ban đầu thành 4 hình chữ nhật con riêng biệt:

1. Góc Trên-Trái (Top-Left): Các ô từ hàng 1 đến hàng r, từ cột 1 đến cột c.

2. Góc Trên-Phải (Top-Right): Các ô từ hàng 1 đến hàng r, từ cột c + 1 đến cột N.

3. Góc Dưới-Trái (Bottom-Left): Các ô từ hàng r + 1 đến hàng M, từ cột 1 đến cột c.

4. Góc Dưới-Phải (Bottom-Right): Các ô từ hàng r + 1 đến hàng M, từ cột c + 1 đến cột N

Yêu cầu: Với mỗi truy vấn, hãy tính và in ra tổng các phần tử của 4 hình chữ nhật con nói trên.

Input:

• Dòng đầu tiên chứa 3 số nguyên M, N, Q (2 ≤ M, N ≤ 1000, 1 ≤ Q ≤ 100,000).

• M dòng tiếp theo, mỗi dòng chứa N số nguyên biểu diễn ma trận A. Giá trị các phần tử | Ai,j| ≤ 1000.

• Q dòng tiếp theo, mỗi dòng chứa 2 số nguyên r, c (1 ≤ r < M, 1 ≤ c < N) biểu thị vị trí cắt.

Output:

• Gồm Q dòng tương ứng với Q truy vấn.

• Mỗi dòng in ra 4 số nguyên lần lượt là tổng của: Trên-Trái, Trên-Phải, Dưới-Trái, Dưới-Phải. Các số cách nhau bởi dấu cách. Giới hạn:

• Thời gian (Time Limit): 1 giây.

• Bộ nhớ (Memory Limit): 256 MB.

• Lưu ý: Thuật toán có đô phức tạp O(M x N) cho mỗi truy vấn sẽ bị quá thời gian (TLE).

Ví dụ:

Input:

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

Output:

4 8 12 16
4 2 24 10

Giải thích ví dụ:

Truy vấn 1 (r=2, c=2):

• Trên-Trái: (1,1) đến (2,2) gồm {1,1,1,1} - Tổng = 4.

• Trên-Phải: (1,3) đến (2,4) gồm {2,2,2,2} -> Tổng = 8.

• Dưới-Trái: (3,1) đến (4,2) gồm {3,3,3,3} -> Tổng = 12.

• Dưới-Phải: (3,3) đến (4,4) gồm {4,4,4,4} -> Tổng = 16.