8216: BZOJ4216:Pig

Memory Limit:3 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

红学姐和黄学长是好朋友。 有一天,黄学长想吃猪肉丸,于是他去找红学姐买猪。红学姐到她的猪圈中赶猪的 时候发现有许多猪逃离了她的猪圈。同时红学姐发现,一个名叫wwf的魔法猪藏在某 个猪圈中施法。然而wwf实在太巨了,红学姐并没有办法捉住它,只好向方老师求救。 为了确定wwf的位置,方老师向红学姐提出了m组询问,每次询问标号在区间[l,r]内 的猪圈剩余的猪的数量和,但红学姐不屑于做这些简单的问题,就把它们交给了你,同 时给了你一台内存较小的电脑。 由于wwf施展了一些奇怪的魔法,所以猪圈中猪的数量可能是负数。


输入格式

第一行两个正整数n,m,t。n表示猪圈数,m表示询问数,t=0表示方老师没有对询问进行加密,t=1表示方老师对询问进行了加密,解密方法如下:   其中^表示异或操作,last_ans表示上一次询问的答案,对于第一次询问,last_ans=0。 第二行n个整数,第i个整数x[i]表示标号为i的猪圈中剩余猪的数量。 接下来m行每行两个正整数l,r表示一组询问。


输出格式

输出m行,第i行表示第i个询问的答案


样例输入

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

样例输出

2
5
-1
5
4

提示

N,M<=500000,|x[i]|<=8000000


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: