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\)).

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.

Ví dụ

Input:

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

Output:

6
3
5