Cho một mảng \(A\) gồm \(N\) số nguyên \(A1, A2, A3... AN\)
Có \(Q\) truy vấn có dạng là hai số \(U\), \(V\) với mỗi truy vấn in ra tổng đoạn từ vị trí \(U\) đến vị trí \(V\). Mỗi kết quả của truy vấn cách nhau một dòng.

Thông số đầu vào

Dòng đầu gồm hai số \(N\), \(Q\) (\(N, Q \le 10^7\))
Dòng thứ hai gồm \(N\) số nguyên dương. \(Q\) dòng tiếp theo, mỗi dòng gồm hai số \(U\), \(V\) (\(U, V \le N\))

Thông số đầu ra

Kết quả theo yêu cầu của bài toán

Ví dụ đầu vào

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

Ví dụ đầu ra

3
5
14