CF983B.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.

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$.

对于长度为 $m$ 的数组 $b$，我们定义函数 $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$ 表示按位异或（XOR）运算。

例如，

$$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$ 表示。答案为所有连续子段 $a_l, a_{l+1}, \ldots, a_r$ 上 $f$ 函数的最大值。

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$).

第一行包含一个整数 $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$）表示。

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

输出 $q$ 行——各查询的答案。

In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.

In second sample, optimal segment for first query are $[3,6]$, for second query — $[2,5]$, for third — $[3,4]$, for fourth — $[1,2]$.

在第一个样例中，两个查询的函数最大值均在等于整个区间的子区间上取得。

在第二个样例中，第一个查询的最优区间为 $[3,6]$，第二个查询为 $[2,5]$，第三个查询为 $[3,4]$，第四个查询为 $[1,2]$。