Mała Owieczka mieszka w małej wiosce rybackiej nad fiordem. Przez $n$ kolejnych dni zapisywała wysokość poziomu morza; $i$-tego dnia ($1\leq i\leq n$) wysokość poziomu morza była dodatnią liczbą całkowitą $h_i$.

Dla wybranego okresu od dnia $l$ do dnia $r$ (włącznie z $l$ oraz $r$) niech:

• $M$ będzie maksymalną wysokością poziomu morza w tym okresie;
• $A$ będzie numerem pierwszego dnia w przedziale $[l,r]$, w którym wysokość poziomu morza osiąga $M$;
• $B$ będzie numerem ostatniego dnia w przedziale $[l,r]$, w którym wysokość poziomu morza osiąga $M$.

Wówczas wartość pływu dla tego okresu definiujemy jako $M\cdot(B-A)$. Zauważ, że jeśli maksymalna wysokość poziomu morza wystąpiła tylko raz, to $A=B$, a wartość pływu wynosi wtedy $0$.

Mała Owieczka zada online $q$ pytań. Każde pytanie określa $l$ oraz $r$, a Twoim zadaniem jest wybranie podokresu $[x,y]$ zawartego w $[l,r]$ (czyli $l\leq x\leq y\leq r$), dla którego wartość pływu jest największa.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), oznaczające odpowiednio łączną liczbę dni obserwacji oraz liczbę zapytań.

Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), oznaczających kolejno wysokość poziomu morza w poszczególnych dniach.

Trzeci wiersz zawiera dwie liczby całkowite $l_1$ oraz $r_1$ ($1\leq l_1\leq r_1\leq n$), oznaczające przedział pierwszego zapytania.

Dla $i$-tego zapytania ($2\leq i\leq q$), zakładając, że $lastans$ jest odpowiedzią na poprzednie zapytanie, przyjmijmy: $$ 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 $$

Wówczas $i$-te zapytanie to w rzeczywistości $l_i=\min(a_i,b_i)$ oraz $r_i=\max(a_i,b_i)$.

Wyjście

Niech $ans_i$ oznacza odpowiedź na $i$-te zapytanie. Wypisz jedną liczbę całkowitą: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Zauważ, że $\oplus$ oznacza operację bitowej różnicy symetrycznej (XOR).

Przykład

Wejście 1

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

Wyjście 1

1

Uwagi

Przedział pierwszego zapytania to $[2,7]$, a optymalny podokres to $[2,4]$, w którym maksymalna wysokość poziomu morza wynosi $8$. W okresie $[2,4]$ wysokość $8$ pojawia się po raz pierwszy dnia $2$, a po raz ostatni dnia $4$, zatem wartość pływu dla tego okresu wynosi $8\times(4-2)=16$.

Kolejne wygenerowane zapytania oraz odpowiedzi na nie to odpowiednio: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Wobec tego szukana suma XOR wynosi $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.