Ovejita vive en un pequeño pueblo pesquero junto a un fiordo. Registró la altura del nivel del mar durante $n$ días consecutivos; en el día $i$ ($1\leq i\leq n$), la altura del nivel del mar es un entero positivo $h_i$.

Para un período seleccionado desde el día $l$ hasta el día $r$ (incluyendo $l$ y $r$), sean:

• $M$ el valor máximo de la altura del nivel del mar en este período;
• $A$ el índice del primer día en $[l,r]$ en que la altura del nivel del mar alcanza $M$;
• $B$ el índice del último día en $[l,r]$ en que la altura del nivel del mar alcanza $M$.

Entonces el valor de marea de este período se define como $M\cdot(B-A)$. Ten en cuenta que si la altura máxima del nivel del mar aparece una sola vez, entonces $A=B$, y en ese caso el valor de marea es $0$.

Ovejita hará $q$ preguntas en línea (online). Cada pregunta dará $l$ y $r$, y debes elegir un subperíodo $[x,y]$ dentro de $[l,r]$ (es decir, $l\leq x\leq y\leq r$) de modo que el valor de marea de dicho período sea máximo.

Entrada

La primera línea contiene dos enteros $n$ y $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), que representan respectivamente el número total de días observados y el número de consultas.

La segunda línea contiene $n$ enteros positivos $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), que representan en orden la altura del nivel del mar de cada día.

La tercera línea contiene dos enteros $l_1$ y $r_1$ ($1\leq l_1\leq r_1\leq n$), que representan el intervalo de la primera consulta.

Para la $i$-ésima consulta ($2\leq i\leq q$), suponiendo que $lastans$ es la respuesta a la consulta anterior, definimos: $$ a_i = \left(l_{i-1} + lastans\cdot37\right) \bmod n + 1,\quad b_i = \left(l_{i-1} + r_{i-1} + lastans\cdot53\right) \bmod n + 1 $$

Entonces la $i$-ésima consulta es en realidad $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$.

Salida

Sea $ans_i$ la respuesta a la $i$-ésima consulta. Imprime un único entero: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Ten en cuenta que $\oplus$ representa la operación XOR bit a bit.

Ejemplos

Entrada 1

8 5
5 8 2 8 4 9 3 9
2 7

Salida 1

1

Nota

El intervalo de la primera consulta es $[2,7]$ y el período óptimo es $[2,4]$, donde la altura máxima del nivel del mar es $8$. En el período $[2,4]$, la altura $8$ aparece por primera vez en el día $2$ y por última vez en el día $4$, por lo que el valor de marea de este período es $8\times(4-2)=16$.

Las consultas generadas posteriormente y sus respuestas respectivas son, en orden: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Por lo tanto, la suma XOR requerida es $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.