Tổng đoạn

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$ và $q$ truy vấn. Mỗi truy vấn đưa ra hai số nguyên $l,r$ ($1\le l\le r\le n$); bạn cần tính tổng

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

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l,r$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng chứa đáp án cho truy vấn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $-{10}^9\le a_i\le {10}^9$
• $1\le l\le r\le n$

Ví dụ

Ghi chú

Đáp án có thể vượt quá phạm vi int 32-bit; hãy dùng số nguyên 64-bit.