Lille Lam bor i en liten fiskerlandsby ved en fjord. Han registrerte havnivåets høyde gjennom $n$ påfølgende dager; på dag $i$ ($1\leq i\leq n$) er havnivåets høyde et positivt heltall $h_i$.
For en valgt tidsperiode fra dag $l$ til dag $r$ (inkludert $l$ og $r$), la:
- $M$ være den maksimale høyden til havnivået i denne perioden;
- $A$ være nummeret på den første dagen i $[l,r]$ der havnivåets høyde når $M$;
- $B$ være nummeret på den siste dagen i $[l,r]$ der havnivåets høyde når $M$.
Da defineres tidevannsverdien for denne perioden som $M\cdot(B-A)$. Merk at dersom den maksimale havnivåhøyden bare forekommer én gang, så er $A=B$, og tidevannsverdien er da $0$.
Lille Lam vil stille $q$ spørsmål online. Hvert spørsmål oppgir $l$ og $r$, og ber deg velge en delperiode $[x,y]$ i $[l,r]$ (det vil si $l\leq x\leq y\leq r$) slik at tidevannsverdien for denne perioden blir størst mulig.
Inndata
Den første linjen inneholder to heltall $n$ og $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), som representerer henholdsvis det totale antallet observerte dager og antallet spørringer.
Den andre linjen inneholder $n$ positive heltall $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), som i rekkefølge representerer havnivåets høyde hver dag.
Den tredje linjen inneholder to heltall $l_1$ og $r_1$ ($1\leq l_1\leq r_1\leq n$), som representerer intervallet for den første spørringen.
For den $i$-te spørringen ($2\leq i\leq q$), anta at $lastans$ er svaret på den forrige spørringen, og la: $$ 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 $$
Da er den $i$-te spørringen egentlig $l_i=\min(a_i,b_i)$ og $r_i=\max(a_i,b_i)$.
Utdata
La $ans_i$ betegne svaret på den $i$-te spørringen. Skriv ut ett enkelt heltall: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.
Merk at $\oplus$ betegner bitvis XOR-operasjon.
Eksempler
Inndata 1
8 5 5 8 2 8 4 9 3 9 2 7
Utdata 1
1
Forklaring
Intervallet for den første spørringen er $[2,7]$, og den optimale perioden er $[2,4]$, hvor den maksimale havnivåhøyden er $8$. I perioden $[2,4]$ forekommer høyden $8$ første gang på dag $2$ og siste gang på dag $4$, så tidevannsverdien for denne perioden er $8\times(4-2)=16$.
De påfølgende genererte spørringene og deres svar i rekkefølge er: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $
Derfor er den etterspurte XOR-summen $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.