对于长度为 $$$m$$$ 的数组 $$$b$$$,我们将函数 $$$f$$$ 定义为
$$$ 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{否则,} \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$$$。答案是数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 的所有连续子段上 $$$f$$$ 的最大值。
输入
第一行包含一个整数 $$$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$$$ 行 — 查询的答案。
示例
输入 #1
3 8 4 1 2 2 3 1 2
输出 #1
5 12
输入 #2
6 1 2 4 8 16 32 4 1 6 2 5 3 4 1 2
输出 #2
60 30 12 3
注意
在两个查询的第一个示例中,函数的最大值在等于整个段的子段上达到。
在第二个示例中,第一个查询的最佳分段是 $$$[3,6]$$$,第二个查询的最佳分段是 $$$[2,5]$$$,第三个查询的最佳分段是 $$$[3,4]$$$,第四个查询的最佳分段是 $$$[1,2]$$$。