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 $n$, which has positive integers, and $q$ queries.

For each query, we will give the values $l$ and $r$ and we are required to solve the problem Interval XOR for the values in the range [$l, 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 $n$ and $q$ ($1 \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 $n$ values, the starting values of the array ($0 \le v_i < 2^{30}$).

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

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

For tests worth $24$ more points, $l = 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