小羊住喺峽灣邊嘅小漁村入面，佢記錄咗連續 $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$ 代表按位異或（XOR）運算。

範例

輸入格式 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$。