KIẾN THỨC

https://docs.google.com/document/d/1f7coVb9LnGAsMQqz8OoyqgSh0loTARv0M9qypFLbork/edit?usp=sharing

BÀI TẬP

Mô tả

Cho một mảng gồm n số nguyên. Có q truy vấn, mỗi truy vấn yêu cầu tính tổng các phần tử từ chỉ số l đến r.

Dữ liệu vào

Dòng 1: Hai số nguyên n và q (1 ≤ n, q ≤ 10⁵)
Dòng 2: n số nguyên a₁, a₂, ..., aₙ (|aᵢ| ≤ 10⁴)
q dòng tiếp theo: Mỗi dòng chứa hai số nguyên l và r (1 ≤ l ≤ r ≤ n)

Dữ liệu ra

In ra q dòng, mỗi dòng là tổng các phần tử từ chỉ số l đến r tương ứng với một truy vấn.

Ví dụ

Ví dụ 1

Input

5 2
1 2 3 4 5
2 4
1 5

Output

9
15

Ví dụ 2

Input

3 1
-2 5 7
1 3

Output

10