Lilla Lammet bor i en liten fiskeby vid en fjord. Han registrerade havsnivåns höjd under $n$ på varandra följande dagar; dag $i$ ($1\leq i\leq n$) är havsnivåns höjd ett positivt heltal $h_i$.

För en vald tidsperiod från dag $l$ till dag $r$ (inklusive $l$ och $r$), låt:

• $M$ vara det maximala värdet på havsnivåns höjd under denna period;
• $A$ vara numret på den första dagen i $[l,r]$ då havsnivåns höjd når $M$;
• $B$ vara numret på den sista dagen i $[l,r]$ då havsnivåns höjd når $M$.

Då definieras denna periods tidvattenvärde som $M\cdot(B-A)$. Observera att om den maximala havsnivåhöjden bara förekommer en gång så är $A=B$, och tidvattenvärdet är då $0$.

Lilla Lammet kommer att ställa $q$ frågor online. Varje fråga ger $l$ och $r$, och du ska välja en delperiod $[x,y]$ inom $[l,r]$ (det vill säga $l\leq x\leq y\leq r$) så att tidvattenvärdet för denna period maximeras.

Indata

Den första raden innehåller två heltal $n$ och $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), som representerar det totala antalet observerade dagar respektive antalet frågor.

Den andra raden innehåller $n$ positiva heltal $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), som i ordning representerar havsnivåns höjd för varje dag.

Den tredje raden innehåller två heltal $l_1$ och $r_1$ ($1\leq l_1\leq r_1\leq n$), som representerar intervallet för den första frågan.

För den $i$:te frågan ($2\leq i\leq q$), anta att $lastans$ är svaret på föregående fråga och låt: $$ 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 $$

Då är den $i$:te frågan i själva verket $l_i=\min(a_i,b_i)$ och $r_i=\max(a_i,b_i)$.

Utdata

Låt $ans_i$ beteckna svaret på den $i$:te frågan. Skriv ut ett enda heltal: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Observera att $\oplus$ betecknar bitvis XOR-operation.

Exempel

Indata 1

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

Utdata 1

1

Förklaring

Intervallet för den första frågan är $[2,7]$ och den optimala perioden är $[2,4]$, där den maximala havsnivåhöjden är $8$. Under perioden $[2,4]$ uppträder höjden $8$ för första gången dag $2$ och för sista gången dag $4$, så tidvattenvärdet för denna period är $8\times(4-2)=16$.

De därefter genererade frågorna och deras respektive svar är i ordning: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Därför är den efterfrågade XOR-summan $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.