Bạn được cho một mảng gồm \(n\) số nguyên và \(q\) truy vấn. Trong mỗi truy vấn, nhiệm vụ của bạn là tính tổng lớn nhất của một dãy con liên tiếp trong đoạn \([a,b]\).

Cho phép dãy con liên tiếp rỗng (có tổng bằng \(0\)).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số phần tử và số truy vấn.

Sau đó có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng.

Cuối cùng có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

In đáp án cho mỗi truy vấn.

Constraints

• \(1 \le n, q\le 2 \cdot 10^5\)

• \(-10^9 \le x_i \le 10^9\)

• \(1 \le a \le b \le n\)

Example

8 4
2 5 1 -2 3 -1 -7 1
2 4
2 5
6 7
4 8

6
7
0
3