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 đấy số \(t_1,t_2,\ldots,t_n\), trong đót \(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ừ 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 \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ị trả về 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 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 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 chứa hai số nguyên dương \(n, q\);
• Dòng thứ hai chứa \(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)\).

Output

• Gồm \(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 file dữ liệu vào.

Scoring

• Subtask \(1\) (\(50\) điểm): \(n, q \leq 50\);
• Subtask \(2\) (\(25\) điểm): \(n, q \leq 5000\);
• Subtask \(3\) (\(25\) điểm): \(n, q \leq 10^5\).

Example

5 2
5 2 3 1 3
1 5
4 5

8
4