You are given an integer sequence \(a_1, a_2, \ldots, a_N\) of length \(N\). There are \(Q\) queries; the \(i\)-th query specifies \(L_i\) and \(R_i\), and you must output \(\sum_{j=L_i}^{R_i} a_j\), the sum of the elements between indices \(L_i\) and \(R_i\) inclusive.

Input

The first line contains two integers \(N\) and \(Q\).

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\).

Each of the next \(Q\) lines contains two integers \(L_i\) and \(R_i\).

Constraints

• \(1 \le N, Q \le 2 \times 10^5\)
• \(1 \le a_i \le 10^4\)
• \(1 \le L_i \le R_i \le N\)

Output

For each query, print one integer on its own line: the sum over that range.

Scoring

There are three subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

• Subtask \(1\) (20 points): \(N, Q \le 5000\).
• Subtask \(2\) (40 points): \(L_i = 1\).
• Subtask \(3\) (40 points): no additional constraints.

Sample Input 1

5 3
1 2 3 4 5
1 3
2 5
4 4

Sample Output 1

6
14
4