Litla Lambið býr í litlu sjávarþorpi við fjörð. Hann skráði hæð sjávarmáls í $n$ daga í röð; á degi $i$ ($1\leq i\leq n$) er hæð sjávarmáls jákvæð heiltala $h_i$.

Fyrir valið tímabil frá degi $l$ til dags $r$ (með $l$ og $r$ meðtöldum), látum:

• $M$ vera hæsta gildi sjávarmáls á þessu tímabili;
• $A$ vera númer fyrsta dagsins í $[l,r]$ þar sem hæð sjávarmáls nær $M$;
• $B$ vera númer síðasta dagsins í $[l,r]$ þar sem hæð sjávarmáls nær $M$.

Þá er sjávarfallagildi þessa tímabils skilgreint sem $M\cdot(B-A)$. Athugið að ef mesta hæð sjávarmáls kemur aðeins fyrir einu sinni, þá er $A=B$ og sjávarfallagildið er þá $0$.

Litla Lambið mun spyrja $q$ spurninga beint (online). Hver spurning gefur $l$ og $r$, og þú átt að velja undirtímabil $[x,y]$ innan $[l,r]$ (þ.e. $l\leq x\leq y\leq r$) þannig að sjávarfallagildi tímabilsins verði sem mest.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), sem tákna annars vegar heildarfjölda athugunardaga og hins vegar fjölda fyrirspurna.

Önnur línan inniheldur $n$ jákvæðar heiltölur $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), sem tákna í röð hæð sjávarmáls á hverjum degi.

Þriðja línan inniheldur tvær heiltölur $l_1$ og $r_1$ ($1\leq l_1\leq r_1\leq n$), sem tákna bil fyrstu fyrirspurnarinnar.

Fyrir $i$-tu fyrirspurnina ($2\leq i\leq q$), látum $lastans$ vera svarið við fyrri fyrirspurn og skilgreinum: $$ 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 $$

Þá er $i$-ta fyrirspurnin í raun $l_i=\min(a_i,b_i)$ og $r_i=\max(a_i,b_i)$.

Úttak

Látum $ans_i$ tákna svarið við $i$-tu fyrirspurninni. Prentið út eina heiltölu: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Athugið að $\oplus$ táknar bitbundna XOR-aðgerð.

Dæmi

Inntak 1

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

Úttak 1

1

Skýring

Bilið fyrir fyrstu fyrirspurnina er $[2,7]$ og besta tímabilið er $[2,4]$, þar sem mesta hæð sjávarmáls er $8$. Á tímabilinu $[2,4]$ kemur hæðin $8$ fyrst fyrir á degi $2$ og síðast á degi $4$, þannig að sjávarfallagildi þessa tímabils er $8\times(4-2)=16$.

Næstu fyrirspurnir sem búnar eru til og svörin við þeim eru í röð: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Því er umbeðin XOR-summa $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.