子羊はフィヨルドのほとりにある小さな漁村に住んでおり、連続する $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)$ と定義されます。なお、海面の高さの最大値が 1 回しか現れない場合、$A=B$ となり、そのときの潮汐値は $0$ になることに注意してください。

子羊はオンラインで $q$ 個の質問をします。各質問では $l$ と $r$ が与えられるので、$[l,r]$ の中から部分期間 $[x,y]$（すなわち $l\leq x\leq y\leq r$）を 1 つ選び、その期間の潮汐値を最大化してください。

入力

1 行目には、観測した総日数と質問の回数を表す 2 つの整数 $n$ と $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$) が与えられます。

2 行目には、各日の海面の高さを順に表す $n$ 個の正の整数 $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$) が与えられます。

3 行目には、最初の質問の区間を表す 2 つの整数 $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)$ となります。

出力

$i$ 番目の質問の答えを $ans_i$ とするとき、1 つの整数 $(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$ となります。