THỰC HÀNH

Trên đường từ nhà bé Na đến nhà bà ngoại có rất nhiều nấm. Một hôm, trên đường đi, bé Na đã hái tất cả số nấm đem sang nhà bà ngoại. Đến nơi, cô, dì, chú, bác xúm lại hỏi bé, những câu hỏi là “trên đoạn đường từ b đến c bé hái được bao nhiêu nấm?”. Do số lượng câu hỏi nhiều nên bé Na rất bối rối, em hãy giúp bé Na trả lời những câu hỏi này nhé.

Biết đoạn đường từ nhà bé Na đến nhà bà ngoại dài N mét, số lượng nấm trên mỗi mét đường là a₁, a₂, …, a_N.

Có M truy vấn, mỗi truy vấn có dạng b_i, c_i, bạn cần trả lời số nấm mà bé Na hái được trên đoạn đường từ mét thứ b_i đến mét thứ c_i.

Dữ liệu vào:

• Dòng đầu là hai số nguyên dương N, M lần lượt là độ dài quãng đường và số lượng truy vấn (hai số cách nhau bởi một khoảng trắng)
• Dòng thứ 2 gồm N số nguyên không âm a₁, a₂, …, a_N là số lượng nấm trên mỗi mét đường (a_i là số lượng nấm trên mét đường thứ i), mỗi số cách nhau bởi một khoảng trắng
• M dòng tiếp theo, dòng thứ i + 2 là hai số nguyên dương b_i, c_i thể hiện truy vấn thứ i

Dữ liệu ra:

Gồm M dòng, dòng thứ i chứa số nguyên là câu trả lời cho truy vấn thứ i (tức là số lượng nấm bé Na hái được trên quãng đường từ mét thứ b_i đến mét thứ c_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 thích:

• Truy vấn 1: Số nấm hái được trên quãng đường từ 1 đến 5 là 1 + 2 + 3 + 4 + 5 = 15
• Truy vấn 2: Số nấm hái được trên quãng đường từ 2 đến 4 là 2 + 3 + 4 = 9

Giới hạn:

• 40% số test (ứng với 40% số điểm của bài) có 1 ≤ N, M ≤ 100, 1≤ b_i ≤ c_i ≤ N, 0 ≤ a_i ≤ 100.
• 40% số test (ứng với 30% số điểm của bài) có 1 ≤ N, M ≤ 10³, 1≤ b_i ≤ c_i ≤ N, 0 ≤ a_i ≤ 10⁵.
• 20% số test (ứng với 30% số điểm của bài) có 1 ≤ N, M ≤ 10⁶, 1≤ b_i ≤ c_i ≤ N, 0 ≤ a_i ≤ 10⁹.