Given an array $A$ of $n$ integers. Let's denote $f(l, r)$ as:
$$f(l,r)=1 \times A_l + 2 \times A_{l+1} + ... + (r - l + 1) \times A_r$$
Given $q$ queries of the form $(l,r)$, find $f(l,r)$.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line contains two integers $l,r$, a query.
### Output
- Print an integer is the answer for each query.
### Constraints
- $1 \le n,q \le 10^5$.
- $|A_i| \le 10^6$.
- $1 \le l,r \le n$.
### Example
Input:
```
3 2
-1 3 2
1 3
2 3
```
Output:
```
11
7
```
