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$