Tổng trên đoạn

Cho mảng \(n\) phần tử (đánh số từ \(1\)) và \(q\) truy vấn; mỗi truy vấn gồm \(u \le v\), hãy tính tổng các phần tử từ vị trí \(u\) đến \(v\).

Input

• Dòng đầu: \(n, q\).
• Dòng hai: \(a_1, \ldots, a_n\).
• \(q\) dòng, mỗi dòng \(u, v\).

Output

In \(q\) dòng, đáp án từng truy vấn.

Constraints

• \(1 \le n, q \le 2 \cdot 10^5\)
• \(1 \le a_i \le 2 \cdot 10^5\)
• \(1 \le u \le v \le n\)

Sample Input

4 3
2 7 1 5
1 4
2 3
4 4

Sample Output

15
8
5