Cho một dãy số nguyên có \(N\) phần tử, mỗi phần tử có giá trị tuyệt đối không quá \(10^9\).

Cho \(Q\) truy vấn, mỗi truy vấn có dạng \(L, R\). Yêu cầu tìm tổng \(A_L + A_{L+1} + ... + A_R\).

Dữ liệu:

• Dòng đầu ghi hai số nguyên dương \(N, Q\) là số phần tử của dãy và số truy vấn.

• Dòng 2: chứa dãy số \(A_1, A_2, …, A_N\)

• \(Q\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(L, R. \)

Kết quả:

• In ra \(Q\) dòng là các câu trả lời.

Sample Input

4 2 
1 2 3 4 
1 1 
2 4

Sample Output

1
9

Giới hạn

• 20% số điểm có \(N, Q ≤ 1000. \)

• 80% số điểm còn lại có \(N, Q ≤ 100000. \)