Cho một dãy gồm ~n~ số nguyên và ~q~ câu hỏi. Mỗi câu hỏi gồm hai số ~l, r~ và yêu cầu tính tổng ~a_l + a_{l+1} + \dots + a_r~. Với ~n, q~ lớn, hãy dùng mảng tổng tiền tố: ~S_i = a_1 + \dots + a_i~ thì tổng đoạn ~[l, r]~ bằng ~S_r - S_{l-1}~.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n, q~ (~1 \le n, q \le 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, \dots, a_n~ (~|a_i| \le 10^9~).

~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~l, r~ (~1 \le l \le r \le n~).

Kết quả

In ra ~q~ dòng, mỗi dòng là tổng của đoạn tương ứng.

Ví dụ

Ví dụ 1

Input:

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

Output:

15
9
3

Ví dụ 2

Input:

1 1
-7
1 1

Output:

-7

Giải thích

Với dãy 1 2 3 4 5 và đoạn ~[2, 4]~: ~2 + 3 + 4 = 9 = S_4 - S_1 = 10 - 1~. Cộng trực tiếp từng đoạn có thể mất ~n \times q = 10^{10}~ phép tính.