Answer inclusive range-sum queries on a fixed array. Query indices are one-based.

Input

The first line contains \(N\) and \(Q\). The second line contains \(N\) integers \(A_i\). Each of the next \(Q\) lines contains \(L\) and \(R\).

The input satisfies:

• \(1 \le N, Q \le 2 * 10^5\)
• \(0 \le A_i \le 10^9\)
• \(1 \le L \le R \le N\)

Output

For each query, print \(A_L+...+A_R\) on its own line.

Example

Input

1 1
5
1 1

Output

5