Petit Mouton vit dans un petit village de pêcheurs au bord d'un fjord. Il a enregistré la hauteur du niveau de la mer pendant $n$ jours consécutifs ; le $i$-ème jour ($1\leq i\leq n$), la hauteur du niveau de la mer est un entier strictement positif $h_i$.

Pour une période choisie allant du jour $l$ au jour $r$ (inclusivement, $l$ et $r$ compris), soient :

• $M$ la valeur maximale de la hauteur du niveau de la mer durant cette période ;
• $A$ le numéro du premier jour dans $[l,r]$ où la hauteur du niveau de la mer atteint $M$ ;
• $B$ le numéro du dernier jour dans $[l,r]$ où la hauteur du niveau de la mer atteint $M$.

Alors la valeur de marée de cette période est définie par $M\cdot(B-A)$. Veuillez noter que si la hauteur maximale du niveau de la mer n'apparaît qu'une seule fois, alors $A=B$, et la valeur de marée vaut alors $0$.

Petit Mouton posera $q$ questions en ligne. Chaque question donnera $l$ et $r$, et vous devrez choisir une sous-période $[x,y]$ dans $[l,r]$ (c'est-à-dire $l\leq x\leq y\leq r$) de sorte que la valeur de marée de cette sous-période soit maximale.

Entrée

La première ligne contient deux entiers $n$ et $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), représentant respectivement le nombre total de jours d'observation et le nombre de requêtes.

La deuxième ligne contient $n$ entiers strictement positifs $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), représentant dans l'ordre la hauteur du niveau de la mer pour chaque jour.

La troisième ligne contient deux entiers $l_1$ et $r_1$ ($1\leq l_1\leq r_1\leq n$), représentant l'intervalle de la première requête.

Pour la $i$-ème requête ($2\leq i\leq q$), en supposant que $lastans$ soit la réponse à la requête précédente, posons : $$ 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 $$

Alors la $i$-ème requête est en réalité $l_i=\min(a_i,b_i)$ et $r_i=\max(a_i,b_i)$.

Sortie

Soit $ans_i$ la réponse à la $i$-ème requête. Veuillez afficher un seul entier : $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Veuillez noter que $\oplus$ désigne l'opération OU exclusif bit à bit (XOR).

Exemples

Entrée 1

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

Sortie 1

1

Remarque

L'intervalle de la première requête est $[2,7]$, et la période optimale est $[2,4]$, où la hauteur maximale du niveau de la mer est $8$. Dans la période $[2,4]$, la hauteur $8$ apparaît pour la première fois le jour $2$ et pour la dernière fois le jour $4$, de sorte que la valeur de marée de cette période est $8\times(4-2)=16$.

Les requêtes générées ensuite ainsi que leurs réponses respectives sont, dans l'ordre : $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Par conséquent, la somme XOR demandée vaut $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.