Description

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ 要写一篇文章，在写文章时，他有 $n$ 个备选的单词，第 $i$ 个单词有一个长度 $a_i$，$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ 可以选择从第 $i$ 个单词开始写作，一共写 $k$ 秒，第 $j$ 秒会写上第 $i+j-1(j\in[1,k])$ 个单词，并且他在写作时每秒都会获得愉悦值，第 $j$ 秒的愉悦值为 $\max_{l=i}^{i+j-1} a_l$，现在，请你帮他算出，他每一次写作获得的愉悦值之和。

一句话题意：给出一个序列和多组询问 $(l,q)$ ，求

数据要求强制在线。

Input Format

第一行，两个数，$n$，$t$，代表词汇个数和问题个数

第二行，$n$ 个数，第 $i$ 个数代表 $a_i$。

接下来 $t$ 行，每行两个数，$u$，$v$，$l=1+(u \oplus lastans)\bmod n$，$q=1+(v \oplus (lastans+1))\bmod (n-l+1)$，代表查询从第 $l$ 秒开始，写作 $q$ 秒的愉悦度之和

$lastans$ 表示上一次查询的答案，初始 $lastans$ 为 $0$。

Output Format

对于每个询问，回答一行，代表答案。

3 2
1 2 3
1 1
1 2

2
3

Hint

样例解释

第一个询问 $1,1$，解密后得到 $l=2,q=1$ ，则按题意可得所求即为区间 $[2,2]$ 的最大值，为 $2$。

第一个询问 $1,2$ ，解密后得到 $l=1,q=2$ ，则所求即为区间 $[1,1]$ 和区间 $[1,2]$ 的最大值之和，为 $3$。

对于 $20\%$ 的数据，$n \leq 1000$，$t \leq 1000$；

对于 $100\%$ 的数据，$n\leq 500000$，$t\leq 500000$，$1 \leq a_i\leq 10^9(i\in [1,n])$。