Dữ liệu tài chính của một công ty trong \(n\) ngày được biểu diễn bằng một dãy số \(t_{1},t_{2},\ldots,t_{n}\), trong đó \(t_{i}\ (1 \leq i \leq n)\) là lượng tiền thu về của ngày thứ \(i\). Lãnh đạo công ty thường xuyên yêu cầu thống kê số liệu về tổng tiền lớn nhất thu được của hai ngày liên tiếp trong các ngày từ \(L\) đến ngày \(R\ (L < R)\), nghĩa là cần tìm giá trị lớn nhất trong các giá trị \((t_{i} + t_{i + 1})\) với \(L \leq i < R\).

Một nhân viên đã truy cập trái phép dữ liệu của công ty và trước mỗi lần lãnh đạo công ty yêu cầu thống kê số liệu, nhân viên sẽ tìm cách đảo ngược một đoạn dữ liệu nào đó trong các ngày từ ngày \(L\) đến ngày \(R\) với mục đích khi thống kê dữ liệu trong đoạn từ ngày \(L\) đến ngày \(R\) thì giá trị càng lớn càng tốt. Ví dụ, nếu đảo ngược đoạn từ ngày \(i\) đến ngày \(j\) (\(1 \leq L \leq i \leq j \leq R \leq n)\) trên dữ liệu ban đầu \(t_{1},t_{2},\ldots,t_{i},t_{i + 1},\ldots,t_{j},\ldots t_{n}\) thì dữ liệu này thay đổi là \(t_{1},t_{2},\ldots,t_{j},\ t_{j - 1},\ldots,t_{i},\ldots,t_{n}\). Sau khi thống kê số liệu xong, người này sẽ lại thay đổi dữ liệu như ban đầu.

Yêu cầu: Cho biết dữ liệu ban đầu là \(t_{1},t_{2},\ldots,t_{n}\) và \(q\) lần yêu cầu thống kê dữ liệu, hãy cho biết số liệu thống kê trả về khi bị can thiệp vào dữ liệu.

Input:

+ Dòng đầu tiên ghi hai số nguyên dương \(n,\ q\);

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên không âm \(t_{1},t_{2},\ldots,t_{n}\ (t_{i} \leq 10^{9})\);

+ Dòng thứ \(k\ (1 \leq k \leq q)\) trong \(q\) dòng sau, mỗi dòng chứa hai số nguyên mô tả yêu cầu thống kê dữ liệu \(L,\ R\ (1 \leq L < R \leq n)\).

Ouput:

+ Ghi ra \(q\) dòng, mỗi dòng chứa một số nguyên là giá trị mà lãnh đạo công ty nhận được khi yêu cầu thống kê dữ liệu tương ứng trong input

Ví dụ:

Giải thích ví dụ:

+ Với yêu cầu thống kê thứ nhất đảo ngược đoạn từ ngày 1 đến ngày 2 để có được dữ liệu mới \(2,\ \mathbf{5,\ 3},\ 1,\ 3\); kết quả thống kê được là \(8\)

+ Với yêu cầu thống kê thứ hai, đảo ngược đoạn từ ngày 4 đến ngày 5 để có được dữ liệu mới \(5,\ 2,\ 3,\ \mathbf{3,\ 1}\); kết quả thống kê được là 4.

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(n,q \leq 50\);

+ Có 25% số test khác tương ứng 25% số điểm có \(n,q \leq 5000\);

+ Có 25% số test còn lại tương ứng 25% số điểm không có ràng buộc gì thêm.