Cho mảng số nguyên A[] gồm N phần tử, có Q truy vấn, mỗi truy vấn là 2 số L, R bạn hãy tính tổng các số từ chỉ số L tới chỉ số R của mảng.

Định dạng đầu vào:

Dòng 1 là N và Q

Dòng 2 là N số nguyên

Q dòng tiếp theo mỗi dòng là 1 truy vấn

Ràng buộc:

1<=N,Q<=10^6

1<=A(i]<=10^9

0<=L<=R<=N-1

Định dạng đầu ra: In ra kết quả của mỗi truy vẫn trên 1 dòng

Input:

11 3
6 5 9 7 7 6 7 7 5 9 7
1 9
1 10
0 8

Output:

62
69
59