Cho một dãy \(A\) gồm \(n\) số nguyên \(a_1, a_2... a_n\) và \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(l, r\). Hãy tìm giá trị của đoạn con liên tiếp có tổng lớn nhất chứa đoạn \(l, r\). hay nói cách khác là cần tìm hai số \(x, y\) thỏa mãn \((1 \le x \le l \le r \le y \le n)\) sao cho tổng các số của đoạn con liên tiếp từ mã số thứ \(x\) đến mỗi số thứ \(y\) lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương \(n, Q (1 \le n, Q \le 10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2,... a_n (|a_i| \le 10^5, 1 \le i \le n)\)
• \(Q\) dòng tiếp theo, mỗi dòng gồm một cặp số nguyên dương \(l, r (1 \le l \le r \le n)\)
• Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra: gồm \(Q\) dòng, mỗi dòng là kết quả tương ứng với cặp số \((l,r)\) theo yêu cầu bài toán.

Ràng buộc:

• 50% số test ứng với 50% số điểm của bài có \((1 \le n \le 10^3, Q=1)\)
• 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.

Input

5 1
1 -2 4 3 -6
2 3

Output

6

Giải thích

- Tổng lớn nhất chứa đoạn [2, 3] là: 1 - 2 + 4 + 3 = 6

Input

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

Output

6
0

Giải thích

- Tổng lớn nhất chứa đoạn [2, 3] là: 2 + 3 - 4 + 5 = 6
- Tổng lớn nhất chứa đoạn [2, 6] là: 2 + 3 - 4 + 5 - 6 = 0