intervalxor2

Time limit: 1s Memory limit: 256MB Input: Output:

Task

You became fond of the problem Interval XOR from the third round, so we decided to give you a more challenging version.

You are given an array of length nn, which has positive integers, and qq queries.

For each query, we will give the values ll and rr and we are required to solve the problem Interval XOR for the values in the range [l,rl, r] in the array. In other words, you will need to find the maximum XOR we can get by removing exactly one value from that interval.

Input

The first line of the input will contain nn and qq (1n,q21051 \le n, q \le 2 * 10^5), the number of values in the array and the number of query operations your program will have to perform.

The next line of the array will have nn values, the starting values of the array (0vi<2300 \le v_i < 2^{30}).

The next qq lines of the array will contain 22 values each, respecting the format given earlier in the statement (1l,rn1 \le l, r \le n).

For tests worth 1414 points, 1n,q21031 \le n, q \le 2 * 10^3.

For tests worth 2424 more points, l=1l = 1 for all the queries.

Output

The output will contain a line for each operation given in the input.

Example 1

stdin

5 4
4 5 2 6 7
1 4
1 3
3 5
1 5

stdout

7
7
5
7

Log in or sign up to be able to send submissions!