小羊居住在峽灣邊的小漁村裡，他記錄了連續 $n$ 天內海平面的高度，第 $i$ 天（$1\leq i\leq n$）的海平面高度是正整數 $h_i$。

對於選定的一個從第 $l$ 天到第 $r$ 天的時段（包含 $l$ 和 $r$），令：

• $M$ 是這個時段裡的海平面高度的最大值；
• $A$ 是 $[l,r]$ 中海平面高度第一次達到 $M$ 的那一天的編號；
• $B$ 是 $[l,r]$ 中海平面高度最後一次達到 $M$ 的那一天的編號。

那麼這個時段的潮汐值就被定義為 $M\cdot(B-A)$。請注意，如果海平面高度最大值只出現了一次，那麼 $A=B$，此時的潮汐值就是 $0$。

小羊會在線地提出 $q$ 個問題。每個問題會給出 $l$ 和 $r$，請你在 $[l,r]$ 中選一個子時段 $[x,y]$（也就是 $l\leq x\leq y\leq r$），使得該時段的潮汐值最大。

輸入格式

第一行包含兩個整數 $n$ 和 $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$)，分別表示觀測的總天數和詢問次數。

第二行包含 $n$ 個正整數 $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$)，依次表示每一天的海平面高度。

第三行包含兩個整數 $l_1$ 和 $r_1$ ($1\leq l_1\leq r_1\leq n$) ，表示第一個詢問的區間。

對於第 $i$ 個詢問 ($2\leq i\leq q$)，假設 $lastans$ 為上一個詢問的答案，令： $$ 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 $$

那麼第 $i$ 個詢問實際上是 $l_i=\min(a_i,b_i)$，$r_i=\max(a_i,b_i)$。

輸出格式

令 $ans_i$ 表示第 $i$ 個詢問的答案，請輸出一個整數：$(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$

請注意，$\oplus$ 表示按位異或運算。

範例

輸入格式 1

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

輸出格式 1

1

說明

第一個詢問的區間是 $[2,7]$，最優時段是 $[2,4]$，其中海平面高度最大值為 $8$。在時段 $[2,4]$ 中，高度 $8$ 第一次出現在第 $2$ 天，最後一次出現在第 $4$ 天，所以該時段的潮汐值是 $8\times(4-2)=16$。

後面生成的各個詢問及其答案依次為： $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

因此要求的異或和為 $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$。