题目背景

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$发怒了，机房的$\textcolor{grey}{\text{deco}}$瑟瑟发抖

题目描述

$\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)$ ，求

数据要求强制在线

输入格式

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

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

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

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

输出格式

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

3 2
1 2 3
1 1
1 2

2
3

提示

样例解释

第一个询问 $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])$