Cho một dãy số nguyên gồm N phần tử nguyên \(A_1\), \(A_2\), …, \(A_N\).
Yêu cầu: Hãy trả lời Q truy vấn có dạng:

• i j: tính tổng các phần tử liên tiếp thuộc đoạn từ i đến j.

Input

• Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ \(10^5\))
• Dòng thứ 2 chứa N số nguyên A1, A2, …, AN (|Ai| ≤ \(10^3\))
• Q dòng tiếp theo mỗi dòng chứa hai số nguyên i, j (1 ≤ i ≤ j ≤ N) thể hiện một câu hỏi truy vấn.

Output

• Chứa Q dòng, mỗi dòng là câu trả lời truy vấn tương ứng trong INPUT.

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

5
2
-4