You are given an integers array $A$ of $n$ elements and $q$ queries, each of the form $(l, r)$, calculate the sum $A_l + A_{l + 1} + ... + A_r$.
### Input
- The first line contains 2 integers $n, q$.
- The second line contains $n$ integers $A_i$.
- Each line of the next $q$ lines contains 2 integers $l, r$, a query.
### Output
- Print $q$ lines, the results of $q$ queries.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le A_i \le 10^9$.
### Example
Input:
```
5 3
1 3 -2 3 4
2 3
1 4
3 5
```
Output:
```
1
5
5
```
