Mô tả bài toán:

Cho một mảng gồm ~ n ~ số nguyên, nhiệm vụ của bạn là xử lý ~ q ~ truy vấn dưới dạng: tổng các giá trị trong đoạn ~[a, b]~ là bao nhiêu?

Input:

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số lượng phần tử và số lượng truy vấn.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các giá trị trong mảng.
• Tiếp theo là ~ q ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: yêu cầu tìm tổng các giá trị trong đoạn ~[a, b]~.

Output:

• In ra kết quả của mỗi truy vấn.

Ràng buộc:

• ~ 1 \leq n, q \leq 2 \cdot 10^5 ~
• ~ 1 \leq x_i \leq 10^9 ~
• ~ 1 \leq a \leq b \leq n ~

Ví dụ:

Input:

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Output:

11
2
24
4

Giải thích:

• Truy vấn 1: Tổng các phần tử từ chỉ số 2 đến 4 là ~ 2 + 4 + 5 = 11 ~.
• Truy vấn 2: Tổng các phần tử từ chỉ số 5 đến 6 là ~ 1 + 1 = 2 ~.
• Truy vấn 3: Tổng các phần tử từ chỉ số 1 đến 8 là ~ 24 ~.
• Truy vấn 4: Tổng các phần tử từ chỉ số 3 đến 3 là ~ 4 ~.