You are given an array \(A\) with \(N\) integers. Please answer the following \(Q\) queries:

Output the sum of the subarray in the range \([L, R]\).

For this problem, python users are recommended to use PyPy instead of CPython

Input Specification

The first line of the input will contain two integers \(N\) and \(Q\) \((1 \le N, Q \le 10^5)\), indicating the number of items and the number of queries.

The next line of the input will contain an integer \(A_i\) ranging from \(0\) to \(10^9\) inclusive, denoting the array \(A\).

The next \(Q\) lines will each contain two integers \(L\) and \(R\) \((1 \le L \le R \le N)\), indicating the \(1\)-indexed indices of the subarray.

Output Specification

Output \(Q\) lines, indicating the answer to the \(i\)-th query.

Sample Input 1

5 2
2 1 0 1 3
1 3
4 4

Sample Output 1

3
1

Sample Explanation 1

For the first query, the sum of the subarray is calculated as \(2 + 1 + 0 = 3\).

For the second query, there is only one value in the subarray. The fourth item in the array is \(1\).