Cho một mảng số nguyên gồm n phần tử. Bạn cần xử lý q truy vấn.

Mỗi truy vấn yêu cầu tính tổng các phần tử trong đoạn từ vị trí a đến b của mảng (tính cả hai đầu).

Input

• Dòng đầu tiên chứa hai số nguyên n và q.
• Dòng thứ hai chứa n số nguyên ~x_1, x_2, ..., x_n~.
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên a và b.

Output

Với mỗi truy vấn, in ra tổng các phần tử từ vị trí a đến b trên một dòng.

Ràng buộc

• ~1 ≤ n, q ≤ 2 × 10^5~
• ~1 ≤ x_i ≤ 10^9~
• ~1 ≤ a ≤ b ≤ n~

Sample Input

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

Sample Output

11
2
24
4