Cho dãy n số nguyên và q câu hỏi, mỗi câu hỏi gồm hai số l, r. Với mỗi câu hỏi hãy tính tổng al + a(l+1) + … + ar.
Minh họa mảng cộng dồn
Dữ liệu vào
Dòng đầu chứa n và q. Dòng thứ hai chứa n số nguyên. Mỗi dòng trong q dòng tiếp theo chứa l và r.
Kết quả
q dòng, mỗi dòng là đáp án một câu hỏi.
Giới hạn
1 ≤ n, q ≤ 10^5; |ai| ≤ 10^9; 1 ≤ l ≤ r ≤ n.
Ví dụ 1 – vào
5 3 1 2 3 4 5 1 3 2 5 4 4
Ví dụ 1 – ra
6 14 4