#P4216. Pig

Pig

题目描述

本题评测时限为 2 秒,内存限制为 10 MB。

红学姐和黄学长是好朋友。

有一天,黄学长想吃猪肉丸,于是他去找红学姐买猪。红学姐到她的猪圈中赶猪的时候发现有许多猪逃离了她的猪圈。同时红学姐发现,一个名叫 wwf 的魔法猪藏在某个猪圈中施法。然而 wwf 实在太巨了,红学姐并没有办法捉住它,只好向方老师求救。

为了确定 wwf 的位置,方老师向红学姐提出了 mm 组询问,每次询问标号在区间 [l,r][l,r] 内的猪圈剩余的猪的数量和,但红学姐不屑于做这些简单的问题,就把它们交给了你,同时给了你一台内存较小的电脑。

由于 wwf 施展了一些奇怪的魔法,所以猪圈中猪的数量可能是负数。

输入格式

第一行三个整数 n,m,tn,m,t,其中 n,mn,m 为正整数。nn 表示猪圈数,mm 表示询问数,t=0t=0 表示方老师没有对询问进行加密,t=1t=1 表示方老师对询问进行了加密,解密方法如下:

$$L=((l\oplus |lastans|)\bmod n)+1, \\ R=((r\oplus |lastans|)\bmod n)+1.$$

解密后的查询区间为 [min⁡(L,R),max⁡(L,R)][\min(L,R),\max(L,R)]。其中 ⊕\oplus 表示异或操作,lastanslastans 表示上一次询问的答案,对于第一次询问,lastans=0lastans=0。

第二行 nn 个整数,第 ii 个整数 xix_i 表示标号为 ii 的猪圈中剩余猪的数量。

接下来 mm 行每行两个正整数 l,rl,r 表示一组询问。

输出格式

输出 mm 行,第 ii 行表示第 ii 个询问的答案。

样例

5 5 1
1 3 -4 5 -3
3 4
1 1
2 3
2 4
3 5
2
5
-1
5
4

数据规模与约定

对于 100%100\% 的数据:N,M≤5×105N,M\le 5\times 10^5,∣xi∣≤8×106|x_i|\le 8\times 10^6。