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)

Mô tả: Cho một xâu S độ dài N chỉ gồm các ký tự + và - . Hãy tìm độ dài của đoạn con liên tiếp dài nhất sao cho số lượng dấu cộng bằng số lượng dấu trừ.

Input:

• Dòng 1: N (1 ≤ N ≤ 10^6).

• Dòng 2: Xâu S.

Output: Độ dài lớn nhất tìm được. Nếu không có in O.

Input:

6
++--+-

Output:

6

Mô tả: Trên trục số, có Q trạm phát sóng phủ đoạn [L, R]. Hãy đếm số điểm nguyên được phủ bởi ít nhất K trạm phát.

Input:

• Dòng 1: N, K, Q (1 ≤ N ≤ 10° là giới hạn tọa độ, 1 ≤ Q < 2 * 10^5).

• Q dòng: L, R (1 ≤ L ≤ R ≤ N).

Output: Số lượng điểm.

Ví dụ:

Input:

10 2 3
1 5
3 8
4 9

Output:

6

Mô tả: Cho N đoạn thẳng [L, R]. Hợp của chúng tạo thành một đoạn liên tục lớn nhưng bị đứt quãng tại đúng 1 điểm nguyên duy nhất nằm giữa các đoạn. Hãy tìm điểm đó.

Input:

• Dòng 1: N (2 ≤ N ≤ 10^5). Tọa độ ≤ 10^6.

• N dòng: L, R.

Output: Tọa độ điểm bị thiếu.

Ví dụ:

Input:

2
1 4
6 10

Output:

5

Cho ma trận A kích thước N × M. Có Q truy vấn. Mỗi truy vấn mô tả một "hình vành khuyên" được tạo bởi một Hình chữ nhật Lớn bao quanh một Hình chữ nhật Bé.

• HCN Lớn có góc trái trên (r1, c1) và phải dưới (r2, c2).

• HCN Bé có góc trái trên (r3, c3) và phải dưới (r4, c4).

• Đảm bảo HCN Bé nằm hoàn toàn bên trong HCN Lớn (r1 ≤ r3 ≤ r4 ≤ r2 và c1 ≤ c3 ≤ c4 ≤ c2).

Hãy tính tổng các phần tử nằm trong HCN Lớn nhưng không nằm trong HCN Bé.

Input:

• Dòng 1: Ba số nguyên N, M, Q (1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 100000).

• N dòng tiếp theo: Mỗi dòng chứa M số nguyên biểu diễn ma trận A (| Ai,j| ≤ 1000).

• Q dòng tiếp theo: Mỗi dòng chứa 8 số nguyên r1, c1, r2, c2, r3, c3, r4, c4.

Output:

• Q dòng, mỗi dòng là kết quả của một truy vấn.

Vi dụ:

Input:

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

Output:

12