Problem Description

FOTILE is given a sequence $A$ of length $N$. To save the Earth, he wants to know the maximum subarray $\rm XOR$ sum within certain intervals.

That is, for each query, you need to compute

To reflect online operations, for a query $(x,y)$:

• $l = \min ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.
• $r = \max ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.

Here $\rm lastans$ is the answer to the previous query, and it is $0$ at the beginning.

Input Format

The first line contains two integers $N$ and $M$.

The second line contains $N$ positive integers, where the $i$-th number is $A_i$, and there may be extra spaces.

The next $M$ lines each contain two numbers $x$ and $y$, representing a query.

Output Format

Output $M$ lines. The $i$-th line contains one positive integer, the answer to the $i$-th query.

3 3
1 4 3 
0 1
0 1
4 3

5
7
7

Hint

For all testdata, $N=12000$, $M=6000$, and $x$, $y$, and $a_i$ are all within the range of signed int.

Translated by ChatGPT 5