Cho một mảng gồm ~n~ số nguyên, nhiệm vụ của bạn là xử lý ~q~ truy vấn có dạng: tổng các phần tử trong đoạn ~[a,b]~ là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên là hai số nguyên ~n~ và ~q~: số phần tử và truy vấn
  
• Dòng thứ hai là ~n~ số nguyên ~x_1,x_2,…,x_n~: các phần tử của mảng
  
• ~q~ dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên ~a~ và ~b~: tổng các phần tử trong đoạn ~[a,b]~ là bao nhiêu?
  

Ràng buộc:

• ~1≤n,q≤2*10^5~
• ~1≤x_i≤10^9~
• ~1≤a≤b≤n~
  

Dữ liệu ra:

• In ra đáp án của mỗi truy vấn

Sample input:

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Sampple output:

11
2
24
4