Maximum XOR for Each Query

f returns the element itself for a single element; otherwise, XOR each pair of adjacent elements to get an array one shorter, and recurse until only one value remains. For each query [l,r], find the maximum f value over all non-empty contiguous subarrays within it. Note that f is not an ordinary range XOR.

This site has made the standard input and output explicit.

输入格式

The first line contains n q, the second line contains n integers, followed by q lines of 0-based l r, with 0≤l≤r<n. On this site 1≤n≤2000, 1≤q≤100000, 0≤a[i]≤2³⁰−1.

输出格式

For each query, output one line with the maximum value.

样例 1

输入：

4 2
1 2 4 8
0 3
1 2

输出：

15
6

样例 2

输入：

3 1
8 1 8
0 2

输出：

9

样例 3

输入：

1 1
0
0 0

输出：

0

样例说明

Example 1: f of the whole array is 15, which is the maximum, and f of subarray [2,4] is 6, so output 15, 6. Example 2: f of the whole array is 8 xor 8=0, but the adjacent pair [8,1] has f=9, so the maximum is 9, not the ordinary XOR of the three numbers. Example 3: f of a single element is just 0.