THỰC HÀNH

Cho một dãy gồm n số nguyên a₁, a₂, …, a_n và q truy vấn, mỗi truy vấn gồm hai số nguyên dương u, v, bạn cần tính tổng các số từ u đến v, tức là a_u + a_{u + 1} + … + a_v.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương n và q.
• Dòng thứ hai chứa n số nguyên không âm a₁, a₂, …, a_n, hai số liên tiếp được ghi cách nhau một khoảng trắng.
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v được ghi cách nhau một khoảng trống

Dữ liệu ra:

Gồm q dòng, dòng thứ i là câu trả lời cho truy vấn thứ i.

Ví dụ:

Dữ liệu vào:
5 2
1 2 3 4 5
1 5
2 4

Dữ liệu ra:
15
9

Giới hạn:1 ≤ n, q ≤ 10⁶; 0 ≤ a_i ≤ 10⁹_.

_{(80% số test có n, q ≤ 1000)}