Pecorella vive in un piccolo villaggio di pescatori vicino a un fiordo. Ha registrato l'altezza del livello del mare per $n$ giorni consecutivi; nel giorno $i$ ($1\leq i\leq n$), l'altezza del livello del mare è un intero positivo $h_i$.

Per un periodo selezionato dal giorno $l$ al giorno $r$ (inclusi $l$ e $r$), siano:

• $M$ il valore massimo dell'altezza del livello del mare in questo periodo;
• $A$ l'indice del primo giorno in $[l,r]$ in cui l'altezza del livello del mare raggiunge $M$;
• $B$ l'indice dell'ultimo giorno in $[l,r]$ in cui l'altezza del livello del mare raggiunge $M$.

Allora il valore di marea di questo periodo è definito come $M\cdot(B-A)$. Si noti che se il valore massimo dell'altezza del livello del mare compare una sola volta, allora $A=B$, e in tal caso il valore di marea è $0$.

Pecorella porrà $q$ domande online. Ogni domanda fornisce $l$ e $r$, e ti chiede di scegliere un sottoperiodo $[x,y]$ all'interno di $[l,r]$ (cioè $l\leq x\leq y\leq r$) in modo da massimizzare il valore di marea di tale periodo.

Input

La prima riga contiene due interi $n$ e $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), che rappresentano rispettivamente il numero totale di giorni di osservazione e il numero di query.

La seconda riga contiene $n$ interi positivi $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), che rappresentano in ordine l'altezza del livello del mare di ciascun giorno.

La terza riga contiene due interi $l_1$ e $r_1$ ($1\leq l_1\leq r_1\leq n$), che rappresentano l'intervallo della prima query.

Per la $i$-esima query ($2\leq i\leq q$), supponendo che $lastans$ sia la risposta alla query precedente, poniamo: $$ 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 $$

Allora la $i$-esima query è effettivamente $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$.

Output

Sia $ans_i$ la risposta alla $i$-esima query; stampa un singolo intero: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Si noti che $\oplus$ indica l'operazione di XOR bit a bit.

Esempi

Input 1

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

Output 1

1

Note

L'intervallo della prima query è $[2,7]$ e il periodo ottimale è $[2,4]$, in cui l'altezza massima del livello del mare è $8$. Nel periodo $[2,4]$, l'altezza $8$ compare per la prima volta il giorno $2$ e per l'ultima volta il giorno $4$, quindi il valore di marea di questo periodo è $8\times(4-2)=16$.

Le query generate successivamente e le rispettive risposte sono, in ordine: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Pertanto, la somma XOR richiesta è $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.