Tý có mảng \(A\) gồm N số nguyên. Hãy thực hiện truy vấn tìm đoạn con liên tiếp có tổng lớn nhất nằm hoàn toàn trong khoảng từ chỉ số l đến chỉ số r (\(tức là \max_{l \le i \le j \le r} \sum_{k=i}^j a_k\)).

Ví dụ

Input:

5 3
2 -1 3 -2 4
1 5
2 4
3 5

Output:

6
3
5

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và Q (\(1 \le N, Q \le 5 \cdot 10^4\)).
• Dòng hai chứa \(N\) số nguyên (\(-10^9 \le a_i $\le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(l, r\) (\(1 \le l \le r $\le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị tổng lớn nhất tìm được.