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.

Đầu vào:

• Dòng 1: 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 l r (1 ≤ l ≤ r ≤ n)

Đầu ra:

• In ra q dòng, mỗi dòng là kết quả của một truy vấn.

Hướng dẫn kỹ thuật:

Sử dụng mảng Prefix Sum prefix[i] = a₁ + a₂ + ... + aᵢ

Test

5 2
1 2 3 4 5
2 4
1 5

9
15

3 1
-2 5 7
1 3

10