Sản Lượng Điều Bình Phước

Mô tả

Bình Phước là thủ phủ điều của cả nước, mỗi năm xuất khẩu hàng trăm ngàn tấn hạt điều nguyên liệu sang thị trường quốc tế. Anh Ba là nhân viên thống kê của một nhà máy chế biến, anh được giao nhiệm vụ tổng hợp dữ liệu sản lượng xuất khẩu theo từng tháng để báo cáo cho ban giám đốc.

Dữ liệu sản lượng (tính bằng tấn) của $N$ tháng liên tiếp đã được lưu vào một mảng cố định. Quá trình thu thập đã hoàn tất, các con số sẽ không thay đổi. Tuy nhiên, ban giám đốc yêu cầu rất nhiều báo cáo, mỗi báo cáo cần biết tổng sản lượng từ tháng $L$ đến tháng $R$. Anh Ba muốn viết một chương trình để trả lời mỗi yêu cầu ngay lập tức thay vì phải cộng lại từ đầu lần nào cũng vậy.

Nhiệm vụ của bạn là giúp anh Ba xây dựng công cụ này: cho trước mảng sản lượng $N$ tháng và $Q$ truy vấn, mỗi truy vấn yêu cầu tính tổng sản lượng từ tháng $L$ đến tháng $R$ (đánh số thứ tự từ $1$).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ $(1 \le N \le 10^5,\ 1 \le Q \le 10^5)$ — số tháng và số truy vấn.

Đầu ra

• Với mỗi truy vấn, in ra một số nguyên trên một dòng — tổng sản lượng điều từ tháng $L$ đến tháng $R$.

Ràng buộc

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$

Ví dụ

Input:

6 3 120 150 200 180 90 110 2 4 1 6 3 5

Output:

530 850 470

Giải thích:

Mảng sản lượng 6 tháng: [120, 150, 200, 180, 90, 110].

Trước tiên, ta tính mảng cộng dồn $S$ trong đó $S[i]$ là tổng từ tháng $1$ đến tháng $i$: [0, 120, 270, 470, 650, 740, 850] (thêm $S[0] = 0$ ở đầu để xử lý biên gọn hơn).

• Truy vấn 1 (tháng 2 đến tháng 4): $S[4] - S[1] = 650 - 120 = 530$. Ta có thể kiểm tra: $150 + 200 + 180 = 530$. Đúng.