Pikku Karitsa asuu pienessä kalastajakylässä vuonon rannalla. Hän kirjasi merenpinnan korkeuden $n$ peräkkäisenä päivänä; päivänä $i$ ($1\leq i\leq n$) merenpinnan korkeus on positiivinen kokonaisluku $h_i$.

Valitulle ajanjaksolle päivästä $l$ päivään $r$ (mukaan lukien $l$ ja $r$) olkoon:

• $M$ tämän ajanjakson merenpinnan korkeuden suurin arvo;
• $A$ sen päivän järjestysnumero välillä $[l,r]$, jolloin merenpinnan korkeus saavuttaa arvon $M$ ensimmäisen kerran;
• $B$ sen päivän järjestysnumero välillä $[l,r]$, jolloin merenpinnan korkeus saavuttaa arvon $M$ viimeisen kerran.

Tällöin tämän ajanjakson vuorovesiarvo määritellään kaavalla $M\cdot(B-A)$. Huomaa, että jos merenpinnan suurin korkeus esiintyy vain kerran, niin $A=B$, jolloin vuorovesiarvo on $0$.

Pikku Karitsa esittää online-tilassa $q$ kysymystä. Jokaisessa kysymyksessä annetaan $l$ ja $r$, ja tehtäväsi on valita välin $[l,r]$ sisältä osaväli $[x,y]$ (eli $l\leq x\leq y\leq r$) siten, että kyseisen ajanjakson vuorovesiarvo on mahdollisimman suuri.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), jotka ilmaisevat havaintopäivien kokonaismäärän ja kyselyiden määrän.

Toinen rivi sisältää $n$ positiivista kokonaislukua $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), jotka ilmaisevat järjestyksessä kunkin päivän merenpinnan korkeuden.

Kolmas rivi sisältää kaksi kokonaislukua $l_1$ ja $r_1$ ($1\leq l_1\leq r_1\leq n$), jotka ilmaisevat ensimmäisen kyselyn välin.

Kyselylle $i$ ($2\leq i\leq q$), olettaen että $lastans$ on edellisen kyselyn vastaus, asetetaan: $$ 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 $$

Tällöin $i$-s kysely on todellisuudessa $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$.

Tuloste

Olkoon $ans_i$ vastaus $i$-nteen kyselyyn. Tulosta yksi kokonaisluku: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Huomaa, että $\oplus$ tarkoittaa bittittäistä XOR-operaatiota.

Esimerkit

Syöte 1

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

Tuloste 1

1

Huomautus

Ensimmäisen kyselyn väli on $[2,7]$ ja optimaalinen ajanjakso on $[2,4]$, jossa merenpinnan suurin korkeus on $8$. Ajanjaksolla $[2,4]$ korkeus $8$ esiintyy ensimmäisen kerran päivänä $2$ ja viimeisen kerran päivänä $4$, joten tämän ajanjakson vuorovesiarvo on $8\times(4-2)=16$.

Seuraavaksi muodostettavat kyselyt ja niiden vastaukset ovat järjestyksessä: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Näin ollen haluttu XOR-summa on $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.