A11845 | XOR-pyramid

For an array $b$ of length $m$ we define the function $f$ as

$ f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases} $ where $\oplus$ is [bitwise exclusive OR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

For example, $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$

You are given an array $a$ and a few queries. Each query is represented as two integers $l$ and $r$ . The answer is the maximum value of $f$ on all continuous subsegments of the array $a_l, a_{l+1}, \ldots, a_r$ .

The first line contains a single integer $n$ ( $1 \le n \le 5000$ ) — the length of $a$ .

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 2^{30}-1$ ) — the elements of the array.

The third line contains a single integer $q$ ( $1 \le q \le 100\,000$ ) — the number of queries.

Each of the next $q$ lines contains a query represented as two integers $l$ , $r$ ( $1 \le l \le r \le n$ ).

Print $q$ lines — the answers for the queries.