Little Sheep lives in a small fishing village by a fjord. He recorded the sea level heights over $n$ consecutive days; on day $i$ ($1\leq i\leq n$), the sea level height is a positive integer $h_i$.

For a chosen period from day $l$ to day $r$ (inclusive of $l$ and $r$), let:

• $M$ be the maximum sea level height during this period;
• $A$ be the index of the day in $[l,r]$ when the sea level height first reaches $M$;
• $B$ be the index of the day in $[l,r]$ when the sea level height last reaches $M$.

Then the tidal value of this period is defined as $M\cdot(B-A)$. Note that if the maximum sea level height appears only once, then $A=B$, and the tidal value is $0$.

Little Sheep will ask $q$ questions online. Each question gives $l$ and $r$, and asks you to choose a sub-period $[x,y]$ within $[l,r]$ (that is, $l\leq x\leq y\leq r$) such that the tidal value of this sub-period is maximized.

Input

The first line contains two integers $n$ and $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), representing the total number of days observed and the number of queries, respectively.

The second line contains $n$ positive integers $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), representing the sea level height on each day in order.

The third line contains two integers $l_1$ and $r_1$ ($1\leq l_1\leq r_1\leq n$), representing the interval of the first query.

For the $i$-th query ($2\leq i\leq q$), let $lastans$ be the answer to the previous query, and define: $$ 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 $$

Then the $i$-th query is actually $l_i=\min(a_i,b_i)$ and $r_i=\max(a_i,b_i)$.

Output

Let $ans_i$ be the answer to the $i$-th query. Output a single integer: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Note that $\oplus$ denotes the bitwise XOR operation.

Examples

Input 1

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

Output 1

1

Note

The interval for the first query is $[2,7]$, and the optimal sub-period is $[2,4]$, where the maximum sea level height is $8$. Within the period $[2,4]$, the height $8$ first appears on day $2$ and last appears on day $4$, so the tidal value of this period is $8\times(4-2)=16$.

The subsequently generated queries and their answers in order are: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Therefore, the required XOR sum is $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.