Migrated from Lutece 2778 故意找茬是吧

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

夏天来了，laduiw 准备去买西瓜犒劳一下作为卷王的自己。于是他走出了电子科技大学西二门，正好看到 MichaelZona 在天桥旁边卖瓜。

L：“哥们儿，这瓜多少钱一斤呐？”

M：“50块钱一斤”

L：“What's up? 你这瓜皮子是金子做的还是瓜粒子是金子做的”

M：“你瞅瞅现在哪有瓜啊，都是大棚的瓜，你嫌贵我还嫌贵呢”

L：“你这瓜保熟不？”

M：“我开水果摊的，我能卖你生瓜蛋子？”

L：“我问你这瓜保熟吗？”

M：“你是故意找茬是吧”

laduiw 觉得 MichaelZona 只会种瓜不会算数，于是出了一道题来决定最后瓜的价格，MichaelZona 觉得自己是卖瓜的算数一定很好，所以接受了这个提议。 laduiw 现在将所有的瓜排成一排，第 $i$ 个瓜初始价格为 $a_i$，对于区间为 $[i,j]$ 的瓜$($即从第 $i$ 个瓜到第 $j$ 个瓜$)$的单价为

$$f(a_{i...j})= \begin{cases} a_i& i=j\\ f(a_i\oplus a_{i+1},a_{i+1}\oplus a_{i+2},...,a_{j-1}\oplus a_j)& i \neq j \end{cases} $$

其中，$“\oplus”$表示按位异或。因此对于价格为$2,3,4$的一排瓜，它们的单价为$f(2,3,4)=f(2\oplus3,3\oplus4)=f(1,7)=f(1\oplus7)=f(6)=6$

laduiw 每次选定买瓜的范围$($一段连续的区间$)$然后让 MichaelZona 自己选择一段该区间的子区间，计算这个子区间瓜的单价，将其作为自己买瓜的价格。MichaelZona 必定想让这个价格最大化，但是觉得这个计算难度超出了自己的能力范围，于是交给了聪明的你，希望你帮他解决。

Input

输入第一行为一个整数 $n$ 表示有 $n$ 个瓜。

输入第二行为 $n$ 个整数，分别表示 $a_i$ 。

输入第三行为一个整数，表示$q$次询问。

接下来输入 $q$ 行，每行两个整数 $l,r$ 表示 laduiw每次询问的区间

Output

输出有 $q$ 行，分别为每次询问的回答。

Samples

6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2

60
30
12
3

Constraints

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

Note

对于第一个询问，最佳子区间为 $[3,6]$；对于第二个询问，最佳子区间为 $[2,5]$；对于第三个询问，最佳子区间为 $[3,4]$；对于第四个询问，最佳子区间为 $[1,2]$。

Resources

2022 UESTC ICPC Training for Dynamic Programming