Nhà bác học nổi tiếng Nicolaus Copernicus sinh ra và lớn lên ở Toruń vào thế kỷ XV. Gần đây, các nhà khảo cổ đã tìm thấy cuốn sổ ghi chép của ông và biết được rằng ông thích dùng các lũy thừa của \(2\) để lưu trữ những số lớn. Ngay cả khi cộng hai lũy thừa của \(2\):

Copernicus cũng tính tổng rồi làm tròn lên đến lũy thừa của \(2\) gần nhất. Nói cách khác, ông tính \(2^a+2^b\) thành \(2^{\max(a,b)+1}\).

Để tính một biểu thức dài hơn có dạng

trước tiên, ông thêm các dấu ngoặc để được một biểu thức có cách đặt ngoặc hợp lệ. Một biểu thức như vậy được định nghĩa như sau: \(2^a\) là một biểu thức có cách đặt ngoặc hợp lệ với mọi số nguyên không âm \(a\); nếu \(E_1\) và \(E_2\) có cách đặt ngoặc hợp lệ thì \((E_1+E_2)\) cũng vậy. Không có biểu thức nào khác được coi là có cách đặt ngoặc hợp lệ.

Chẳng hạn, có thể thêm dấu ngoặc vào biểu thức \(2^5+2^4+2^4+2^4+2^5\) để được

Sau đó, ông tính giá trị của biểu thức đã đặt ngoặc bằng cách thực hiện từng phép cộng theo quy tắc trên. Kết quả có thể khác nhau tùy theo cách đặt ngoặc. Ví dụ, dưới đây là hai cách tính biểu thức \(2^5+2^4+2^4+2^4+2^5\):

Trang đầu tiên trong cuốn sổ của Copernicus chỉ chứa một biểu thức, được gọi là biểu thức chính:

Những trang sau nhắc đến các đoạn của biểu thức chính, có dạng

với \(1\le\ell\le r\le n\).

Bạn chưa rõ ý nghĩa của những đoạn này, nhưng đoán rằng với mỗi đoạn, bạn cần tìm kết quả nhỏ nhất có thể nhận được bằng cách đặt ngoặc và tính toán theo quy tắc trên. Mỗi đoạn được xét độc lập với các đoạn khác.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\), lần lượt là số số hạng trong biểu thức chính và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số mũ của lũy thừa của \(2\) thứ \(i\) trong biểu thức chính.

\(q\) dòng tiếp theo mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(\ell\) và \(r\), chỉ đoạn bắt đầu ở lũy thừa của \(2\) thứ \(\ell\) và kết thúc ở lũy thừa của \(2\) thứ \(r\) trong biểu thức chính.

Dữ liệu ra

In ra \(q\) dòng. Dòng thứ \(i\) chứa số mũ của lũy thừa của \(2\) nhỏ nhất có thể nhận được khi tính đoạn trong truy vấn thứ \(i\) theo quy tắc đã mô tả. Chỉ in số mũ, không in giá trị của lũy thừa.

Ràng buộc

• \(1\le n,q\le 300\,000\).
• \(0\le a_i\le 10^6\) với mọi \(1\le i\le n\).
• \(1\le\ell\le r\le n\) trong mỗi truy vấn.

Phân nhóm

1. \(6\) điểm: \(n\le 8\) và \(q\le 10\).
2. \(8\) điểm: \(n\le 200\).
3. \(23\) điểm: \(n,q\le 2000\).
4. \(22\) điểm: \(a_i\le 20\) với mọi \(1\le i\le n\).
5. \(41\) điểm: không có ràng buộc bổ sung.

Ví dụ

8 4
2 4 2 5 4 4 4 5
4 8
1 4
2 5
1 7

7
7
7
8