Cho một mảng số nguyên A gồm N phần tử. Có Q truy vấn, mỗi truy vấn gồm hai số L và R.

Nhiệm vụ của bạn là tính tổng các phần tử của mảng từ vị trí L đến R.

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 của mảng A.
• Q dòng tiếp theo, mỗi dòng chứa hai số L và R.

Output

Với mỗi truy vấn, in ra tổng các phần tử từ chỉ số L đến R trên một dòng.

Ràng buộc

• ~1 ≤ N, Q ≤ 10^6~
• ~1 ≤ A[i] ≤ 10^9~
• ~0 ≤ L ≤ R ≤ N - 1~

Sample Input

11 3
6 5 9 7 7 6 7 7 5 9 7
1 9
1 10
0 8

Sample Output

62
69
59