Căng tin khu A ghi lại kết quả kinh doanh trong ~n~ ngày liên tiếp: ngày thứ ~i~ thu về ~a_i~ nghìn đồng tiền lãi. Giá trị ~a_i~ có thể âm – khi đó căng tin bị lỗ ~|a_i|~ nghìn đồng trong ngày thứ ~i~.

Để lập báo cáo, chị quản lý đặt ra ~q~ câu hỏi. Mỗi câu hỏi gồm hai số ~l~ và ~r~: tính từ ngày ~l~ đến hết ngày ~r~ (kể cả hai ngày này), tổng cộng căng tin lãi bao nhiêu? Nói cách khác, cần tính

$$a_l + a_{l+1} + \cdots + a_r .$$

Yêu cầu

Hãy trả lời cả ~q~ câu hỏi.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~q~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~;
• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~l~ và ~r~ mô tả một câu hỏi.

Kết quả ra

Ghi ra ~q~ dòng, mỗi dòng một số nguyên là câu trả lời cho một câu hỏi, theo đúng thứ tự các câu hỏi trong dữ liệu vào. Tổng âm thì ghi kèm dấu trừ ở phía trước.

Ràng buộc

~1 \le n, q \le 2 \cdot 10^5~; ~-10^9 \le a_i \le 10^9~; ~1 \le l \le r \le n~.

• Subtask 1 (30% số điểm – test 01–06): ~n, q \le 1000~;
• Subtask 2 (20% số điểm – test 07–10): mọi truy vấn có ~l = 1~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

6 3
5 -3 4 -6 2 7
1 6
2 4
4 4

Kết quả ra mẫu 1

9
-5
-6

Giải thích

Câu hỏi thứ nhất: ~5 - 3 + 4 - 6 + 2 + 7 = 9~. Câu hỏi thứ hai: ~-3 + 4 - 6 = -5~, tức là ba ngày từ ~2~ đến ~4~ căng tin lỗ ~5~ nghìn đồng. Câu hỏi thứ ba chỉ gồm ngày ~4~: ~-6~.