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, mỗi truy vấn yêu cầu tính tổng các giá trị trong đoạn từ chỉ số ~a~ đến ~b~.

Đầu vào:

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: số lượng phần tử trong mảng và số lượng truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~x₁, x₂, ..., xₙ~: là các giá trị trong mảng.

Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~a~ và ~b~: yêu cầu tính tổng các phần tử từ vị trí a đến b (tính cả hai đầu).

Đầu ra:

Với mỗi truy vấn, in ra một dòng chứa tổng các phần tử từ vị trí a đến b.

Ràng buộc:

~1 \le n,q \le 2 \cdot 10^5~

~1 \le x_i \le 10^9~

~1 \le a \le b \le n~

Ví dụ :

Input:

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

Output:

11
2
24
4