Cho một dãy số gồm ~n~ phần tử nguyên ~a_1, a_2, \cdots, a_n~ và bạn phải trả lời ~q~ truy vấn, mỗi truy vấn có dạng hai số ~(l, r)~ yêu cầu tính tổng ~a_l~ ~+~ ~a_{l + 1}~ ~+~ ~\cdots~ ~+~ ~a_r~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 10^5~) — số phần tử và số truy vấn.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ (~-10^9 \le a_i \le 10^9~) — dãy ~a~.

Trong ~q~ dòng tiếp theo, mỗi dòng gồm hai số ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~) — truy vấn thứ ~i~.

Output

In ra ~q~ dòng là đáp án cho ~q~ truy vấn.

Sample Input 1

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

Sample Output 1

1
5
5

Notes

Trong các truy vấn:

• Truy vấn ~1~: ~a_2 + a_3 = 3 - 2 = 1~;

• Truy vấn ~2~: ~a_1 + a_2 + a_3 + a_4 = 1 + 3 - 2 + 3 = 5~;

• Truy vấn ~3~: ~a_3 + a_4 + a_5 = -2 + 3 + 4 = 5~.