Mivik 的神力

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的正整数序列 $a$。一次询问给出起点 $l$ 和长度 $q$，其答案为

$$\sum_{i=l}^{l+q-1}\max_{l\le j\le i}a_j.$$

为了强制在线，输入的每组询问由 $u,v$ 加密。设上一次询问的答案为 $lastans$，初始时 $lastans=0$，则本次实际询问为

$$l=1+((u\mathbin{\mathrm{xor}}lastans)\bmod n),$$ $$q=1+((v\mathbin{\mathrm{xor}}(lastans+1))\bmod(n-l+1)).$$

输出本次答案后，再令 $lastans$ 等于该答案。

输入格式

第一行输入两个整数 $n,t$，表示序列长度和询问数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $t$ 行，每行输入两个非负整数 $u,v$，表示一组加密询问。

输出格式

对每个询问输出一行一个整数，表示答案。

样例输入 1

3 2
1 2 3
1 1
1 2

样例输出 1

2
3

数据范围

对于所有数据，$1\le n,t\le5\times10^5$，$1\le a_i\le10^9$，$0\le u,v<2^{63}$。

子任务编号	分值	特殊限制
1	24	$n,t\le2000$
2	36	序列 $a$ 中不同取值不超过 $50$ 个
3	40	无特殊限制