Sau những thử thách khó khăn, Long cuối cùng cũng tìm được manh mối tại sao nhà toán học lại biến mất một cách bất ngờ như vậy. Cậu tìm thấy một con robot giúp việc, từng là người thân tín nhất với nhà toán học. Chắc chắn nó đã chứng kiến tất cả những gì đã xảy ra trong ngôi nhà này. Tuy nhiên, để khởi động nó, cậu cần phải tìm đã được mật khẩu kích hoạt. Con robot này hiển thị một dãy số gồm N số nguyên trên màn hình. Sau đó, nó sẽ lần lượt hỏi Long Q câu hỏi, mỗi câu hỏi sẽ gồm 2 số nguyên dương L và R:

“Hãy tìm giá trị đoạn con liên tiếp có tổng lớn nhất chứa đoạn [L, R]. Nói cách khác, tìm tổng từ x tới y với 1 ≤ x ≤ L ≤ R ≤ y ≤ N sao cho tổng này là lớn nhất có thể.”

Đây quả thật là thử thách hóc búa, hãy giúp Long nhé.

Dữ liệu: Vào từ file LONGMAX.INP gồm:

+ Dòng đầu tiên gồm 2 số nguyên dương N, Q (N, Q ≤ 10⁵);

+ Dòng tiếp theo gồm N số a_i (|a_i| ≤ 10⁵);

+ Q dòng tiếp theo, mỗi dòng là 2 cặp số L, R

Kết quả: Ghi ra file LONGMAX.OUT Q dòng, mỗi dòng là kết quả của mỗi câu hỏi của Robot.

Ví dụ:

Ràng buộc:

+ Có 20% số điểm N ≤ 10³ và Q = 1;

+ Có 80% số điểm còn lại không có ràng buộc gì thêm.