Given an array, \(A\), containing \(n\) integers, \(a_{1}, a_{2}, a_{3}, ... a_{n}\), you have to answer \(q\) queries.

For each query you will be given a one-indexed range \([l, r]\), \(l \leq r\), and your answer to each query should be: \(\sum_{i = l}^{r} (r - i + 1).a[i]\)

For example, if \(A = [6, 10, -9, 11, 12] \), for \(l = 2\), and \(r = 5\):

\((5 - 2 + 1) * 10 + (5 - 3 + 1) * -9 + (5 - 4 + 1) * 11 + (5 - 5 + 1) * 12 = \)

\(4 * 10 + 3 * -9 + 2 * 11 + 1 * 12 = 47\)

NOTE: The answer to a query may not fit a 32-bit integer type.

Input format

The first line contains two integers \(n\), and \(q\) - denoting the number of integers in \(A\), and the number of queries respectively.
The next line contains \(n\) integers, \(a_{i}\) - denoting the values of the integers in \(A\).
The \(i^{th}\) line among next \(q\) lines each contain two integers, \(l_{i}\), and \(r_{i}\) - denoting the indices to be queried for the \(i^{th}\) query.

Output format
Your program should output \(q\) lines, and the \(i^{th}\)of these lines should be the answer to the \(i^{th}\) query.

Constraints

\(1 \leq n, q \leq 10^5\\ \\-10^7\leq A_i \le 10^7\\ \\1 \leq l_i \leq r_i \leq n\)