Kim tự tháp XOR

Với một dãy $b$ gồm $m$ phần tử, định nghĩa hàm $f$ như sau:

$$f(b)=\{\begin{array}{cc}{b}_1\hfill & \text{nếu }m=1\hfill \\ f(b_1\oplus b_2,b_2\oplus b_3,\dots ,b_{m-1}\oplus b_m)\hfill & \text{nếu }m>1\hfill \end{array}$$

trong đó $\oplus$ là phép XOR (hoặc loại trừ theo bit).

Nói cách khác, ta liên tục thay dãy hiện tại bằng dãy các phép XOR của những cặp phần tử liền kề, cho tới khi chỉ còn một số. Số đó chính là giá trị của $f$.

Ví dụ: $$f(1,2,4,8)=f(1\oplus 2,2\oplus 4,4\oplus 8)=f(3,6,12)=f(5,10)=f(15)=15.$$

Cho một dãy $a$ gồm $n$ phần tử và $q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $l$ và $r$. Với mỗi truy vấn, hãy tìm giá trị lớn nhất của $f$ trên mọi đoạn con liên tiếp của dãy $a_l,a_{l+1},\dots ,a_r$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: độ dài dãy $a$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $q$: số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Ràng buộc

• $1\le n\le 5000$
• $0\le a_i\le 2^{30}-1$
• $1\le q\le {10}^5$
• $1\le l\le r\le n$

Ví dụ