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,\dots,t_n$, trong đó $t_i\ (1\le i\le 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ừ ngày $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\le 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ị trả về càng lớn càng tốt. Vi dụ, nếu đảo ngược đoạn từ ngày $i$ đến ngày $j\ (1\le L\le i\le j\le R\le n)$ trên dữ liệu ban đầu $t_1,t_2,\dots,t_i,t_{i+1},\dots,t_j\dots,t_n$ thì dữ liệu thay đổi là $t_1,t_2,\dots,t_j,t_{j-1},\dots,t_i\dots,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,\dots,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.

5 2
5 2 3 1 3
1 5
4 5

8
4