Das kleine Schaf lebt in einem kleinen Fischerdorf an einem Fjord. Es hat an $n$ aufeinanderfolgenden Tagen die Höhe des Meeresspiegels aufgezeichnet; am $i$-ten Tag ($1\leq i\leq n$) beträgt die Höhe des Meeresspiegels eine positive ganze Zahl $h_i$.

Für einen ausgewählten Zeitraum vom $l$-ten Tag bis zum $r$-ten Tag (einschließlich $l$ und $r$) seien:

• $M$ das Maximum der Meeresspiegelhöhe in diesem Zeitraum;
• $A$ die Nummer des ersten Tages in $[l,r]$, an dem die Meeresspiegelhöhe den Wert $M$ erreicht;
• $B$ die Nummer des letzten Tages in $[l,r]$, an dem die Meeresspiegelhöhe den Wert $M$ erreicht.

Dann ist der Gezeitenwert dieses Zeitraums definiert als $M\cdot(B-A)$. Bitte beachte: Wenn das Maximum der Meeresspiegelhöhe nur einmal vorkommt, gilt $A=B$, und der Gezeitenwert beträgt in diesem Fall $0$.

Das kleine Schaf stellt online $q$ Fragen. Jede Frage gibt $l$ und $r$ vor; bitte wähle in $[l,r]$ einen Teilzeitraum $[x,y]$ (also $l\leq x\leq y\leq r$), sodass der Gezeitenwert dieses Zeitraums maximal wird.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), die die Gesamtzahl der beobachteten Tage bzw. die Anzahl der Anfragen angeben.

Die zweite Zeile enthält $n$ positive ganze Zahlen $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), die der Reihe nach die Höhe des Meeresspiegels an jedem Tag angeben.

Die dritte Zeile enthält zwei ganze Zahlen $l_1$ und $r_1$ ($1\leq l_1\leq r_1\leq n$), die das Intervall der ersten Anfrage angeben.

Für die $i$-te Anfrage ($2\leq i\leq q$) sei $lastans$ die Antwort auf die vorherige Anfrage, und es gelte: $$ 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 $$

Dann lautet die $i$-te Anfrage tatsächlich $l_i=\min(a_i,b_i)$ und $r_i=\max(a_i,b_i)$.

Ausgabe

Sei $ans_i$ die Antwort auf die $i$-te Anfrage. Gib eine einzige ganze Zahl aus: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Bitte beachte, dass $\oplus$ die bitweise XOR-Verknüpfung bezeichnet.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Das Intervall der ersten Anfrage ist $[2,7]$ und der optimale Zeitraum ist $[2,4]$, in dem die maximale Meeresspiegelhöhe $8$ beträgt. Im Zeitraum $[2,4]$ tritt die Höhe $8$ zum ersten Mal am Tag $2$ und zum letzten Mal am Tag $4$ auf, sodass der Gezeitenwert dieses Zeitraums $8\times(4-2)=16$ ist.

Die anschließend generierten Anfragen und ihre Antworten lauten der Reihe nach: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Daher beträgt die gesuchte XOR-Summe $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.