B. XOR-пирамида
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ длины $$$m$$$ определим функцию $$$f$$$:

$$$ f(b) = \begin{cases} b[1] & \quad \text{если } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{в остальных случаях,} \end{cases} $$$

где $$$\oplus$$$ — операция побитового исключающего ИЛИ.

К примеру, $$$f(1,2,4,8)=f(1\oplus2,2\oplus4,4\oplus8)=f(3,6,12)=f(3\oplus6,6\oplus12)=f(5,10)=f(5\oplus10)=f(15)=15$$$

Вам дан массив $$$a$$$ и несколько запросов. Каждый запрос — пара целых чисел $$$l$$$ и $$$r$$$. В качестве ответа на запрос вам нужно вывести максимальное значение функции $$$f$$$ по всем непрерывным подотрезкам массива $$$a_l, a_{l+1}, \ldots, a_r$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — число элементов в массиве $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^{30}-1$$$) — элементы массива.

Третья строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 100\,000$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит запрос — два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$).

Выходные данные

Выведите $$$q$$$ строк — ответы на запросы.

Примеры
Входные данные
3
8 4 1
2
2 3
1 2
Выходные данные
5
12
Входные данные
6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2
Выходные данные
60
30
12
3
Примечание

В первом примере оптимально в обоих запросах взять отрезок целиком.

Во втором примере оптимальный отрезок для первого запроса — $$$[3,6]$$$, для второго — $$$[2,5]$$$, для третьего — $$$[3,4]$$$, для четвертого — $$$[1,2]$$$.