Cho mảng \(A\) gồm \(N\) số nguyên và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L\) và \(R\). Nhiệm vụ của bạn là in ra tổng các phần tử của mảng \(A\) trong đoạn từ chỉ số \(L\) đến \(R\).

Input

• Dòng 1: Hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
• Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo: Mỗi dòng gồm 2 số \(L, R\) (\(1 \le L \le R \le N\)).

Output

• Với mỗi truy vấn, in ra tổng đoạn \([L, R]\) trên một dòng.

Example

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

11
2
24
4

Scoring

• Subtask 1 (\(50\%\) số điểm): \(N, Q \le 1000\).
• Subtask 2 (\(50\%\) số điểm): Ràng buộc gốc \(N, Q \le 2 \cdot 10^5\).