You are given array $A$ of $n$ integers.
There are $q$ queries of the form $(l, r)$, find maximum value of $A_i+A_{i+1}+...+A_j$ with $l \le i \le j \le r$.
### Input
- The first line contains 2 integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines, each line contains 2 integers $l, r$, a query.
### Output
- Print $q$ integers, the answer to $q$ queries.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le l, r \le n$.
- $0 \le |A_i| \le 10^9$.
### Example
Input:
```
3
-1 2 3
1
1 2
```
Output:
```
2
```
