Cho mảng A gồm n số nguyên và q truy vấn có dạng (l,r), tính tổng: A[l]+A[l+1]+…+A[r].

Input

Dòng đầu gồm 2 số nguyên dương n,q.

Dòng thứ hai gồm n số nguyên Ai.Mỗi dòng trong q dòng tiếp theo gồm 2 số nguyên l,r thể hiện một truy vấn.

Output

q dòng mỗi dòng một số nguyên là kết quả cho các truy vấn.

Điều kiện:

    1≤n,q≤10^5.
    1≤Ai≤10^9.

Ví dụ

Input:

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

Output:

1
5
5