Cho một dãy gồm N số nguyên dương A1, A2,…, AN. (N ≤ 105, Ai ≤108).
Cho Q truy vấn có dạng (u,v). Với mỗi truy vấn (u,v) trả lời tổng các phần tử của mảng A từ phần tử thứ u đến phần tử thứ v.
Input:
Dòng đầu chứa số N, Q (1 ≤ Q ≤ 105)
Dòng thứ hai chứa N số nguyên dương A1, A2,…, AN. Q dòng tiếp theo ghi 2 số nguyên u,v (1 ≤ u ≤ v ≤ 105)
Output: Gồm Q dòng, mỗi dòng ghi trả lời tương ứng với mỗi truy vấn..
Input
8 4
1 4 5 1 4 3 3 4
1 4
3 5
6 7
5 8
Output
11
10
6
14