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\).
  

Dữ liệu

• 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 \(A_1, A_2, …, A_N\) \((|A_i| ≤ 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.
  

Kết quả

• Chứa \(Q\) dòng, mỗi dòng là câu trả lời truy vấn tương ứng trong dữ liệu đầu vào.

input

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

output

5
2
-4

Giải thích
Dãy có 5 phần tử và 3 truy vấn

• Truy vấn 1: tính tổng các phần từ thứ 1 đến thứ 4 là: 1 + 3 + (-4) + 5 = 5
• Tương tự như vậy ta được kết quả của 2 truy vấn còn lại là 2 và -4