Description

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ wants to write an article. While writing, he has $n$ candidate words. The $i$-th word has length $a_i$. $\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ can choose to start writing from the $i$-th word and write for a total of $k$ seconds. In the $j$-th second, he writes the $(i+j-1)$-th word $(j\in[1,k])$. While writing, he gains happiness points every second. The happiness points in the $j$-th second are $\max_{l=i}^{i+j-1} a_l$. Now please help him compute, for each writing process, the sum of happiness points he gains.

One-sentence statement: Given a sequence and multiple queries $(l,q)$, compute

The testdata requires mandatory online processing.

Input Format

The first line contains two integers $n$ and $t$, representing the number of words and the number of queries.

The second line contains $n$ integers. The $i$-th integer represents $a_i$.

In the next $t$ lines, each line contains two integers $u$ and $v$, where $l=1+(u \oplus lastans)\bmod n$ and $q=1+(v \oplus (lastans+1))\bmod (n-l+1)$. This represents a query asking for the sum of happiness points when starting from the $l$-th second and writing for $q$ seconds.

$lastans$ denotes the answer to the previous query, with initial value $lastans=0$.

Output Format

For each query, output one line containing the answer.

3 2
1 2 3
1 1
1 2

2
3

Hint

Sample Explanation

For the first query $1,1$, after decoding we get $l=2,q=1$. Then according to the statement, the answer is the maximum value on interval $[2,2]$, which is $2$.

For the first query $1,2$, after decoding we get $l=1,q=2$. Then the answer is the sum of the maximum values on intervals $[1,1]$ and $[1,2]$, which is $3$.

For $20\%$ of the testdata, $n \leq 1000$ and $t \leq 1000$.

For $100\%$ of the testdata, $n\leq 500000$, $t\leq 500000$, and $1 \leq a_i\leq 10^9(i\in [1,n])$.

Translated by ChatGPT 5