小羊居住在峡湾边的小渔村里，他记录了连续 $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$。