Для массива \(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\).
Выходные данные
Выведите \(q\) строк — ответы на запросы.
Примечание
В первом примере оптимально в обоих запросах взять отрезок целиком.
Во втором примере оптимальный отрезок для первого запроса — \([3,6]\), для второго — \([2,5]\), для третьего — \([3,4]\), для четвертого — \([1,2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
8 4 1
2
2 3
1 2
|
5
12
|
|
2
|
6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2
|
60
30
12
3
|