Điều chỉnh đồng loạt theo khoảng

Bối cảnh và bài toán

Một bảng định mức gồm n vị trí thường xuyên nhận các đợt hiệu chỉnh đồng loạt trên một đoạn liên tiếp. Sau các đợt cập nhật, hệ thống cần truy vấn nhanh giá trị hiện thời tại một vị trí cụ thể.

Yêu cầu

Hỗ trợ tăng toàn bộ phần tử trên đoạn và truy vấn một điểm.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa mảng ban đầu.
• Truy vấn loại 1 a b u: cộng u vào mọi vị trí trong [a,b].
• Truy vấn loại 2 k: in giá trị hiện tại tại k.

Output

In đáp án cho mỗi truy vấn loại 2.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• 1 <= a[i], u <= 10^9
• 1 <= a <= b <= n
• 1 <= k <= n

Chấm điểm

Ví dụ 1

Input

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

Output

5
6

Giải thích. Sau khi cộng 1 cho đoạn 2..5, vị trí 4 tăng từ 5 lên 6.

Ví dụ 2

Input

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

Output

4
6
4

Giải thích. Hai đợt cập nhật chồng lấn tại vị trí 2 và 3.

Thông tin bài tập

Nguồn: Phỏng theo CSES – Range Update Queries.