Cho mảng ~A_1, A_2, \dots, A_n~ và ~q~ truy vấn. Mỗi truy vấn có dạng u v yêu cầu tính tổng ~A_u + A_{u+1} + \dots + A_v~.

Yêu cầu: Trả lời tất cả truy vấn và in ra đáp án.

Dữ liệu:

Vào từ file văn bản SUMQUERY.INP:

• Dòng đầu tiên chứa hai số nguyên ~n, q~.
• Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~.
• ~q~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một truy vấn.

Dữ liệu đảm bảo ~1 \le n, q \le 10^5~, ~1 \le u \le v \le n~ và ~|A_i| \le 10^9~.

Kết quả

Ghi vào file văn bản SUMQUERY.OUT ~q~ dòng chứa câu trả lời của các truy vấn.

Example

Input

5 2
3 -5 1 7 8
1 3
2 5

Output

-1
11