Maximum Subarray XOR with Online Queries

FOTILE has an array A of length N, and to save the Earth, he wants to know the maximum contiguous XOR sum within a specified interval. For any query, you are required to compute:

$$ \max_{l \leq i \leq j \leq r} \bigoplus_{k=i}^{j} a_k $$

To support online queries, each query is given as two integers x and y. Define:

• l = min ( (((x+lastans) mod N)+1), (((y+lastans) mod N)+1) )
• r = max ( (((x+lastans) mod N)+1), (((y+lastans) mod N)+1) )

Here, lastans is the answer of the previous query, and is initially 0. For the segment A[l..r], find the maximum value of the XOR of any contiguous subarray.

For example, if A = [1,2,3,4,5] and a query results in l=1 and r=3, then you should compute:

max { 1, 1^2, 1^2^3, 2, 2^3, 3 } = 3

Your task is to process Q queries on the sequence and output the maximum contiguous subarray XOR sum for each query.

inputFormat

The first line contains two integers N and Q --- the length of the sequence and the number of queries.

The second line contains N integers: a₁, a₂, ..., a_N, which represent the sequence.

Each of the next Q lines contains two integers x and y representing a query.

outputFormat

For each query, output one line containing the maximum contiguous subarray XOR for the interval determined by the query.

sample

5 3
1 2 3 4 5
0 2
1 1
2 4

3
5
7