#104216. [BZOJ 4216] Pig

请注意本题特殊的空间限制。

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

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

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

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

第一行两个正整数 。 表示猪圈数， 表示询问数， 表示方老师没有对询问进行加密， 表示方老师对询问进行了加密，解密方法如下：

其中 表示异或操作， 表示上一次询问的答案，对于第一次询问，。

第二行 个整数，第 个整数 表示标号为 的猪圈中剩余猪的数量。

接下来 行每行两个正整数 表示一组询问。

输出 行，第 行表示第 个询问的答案。

样例

样例输入 #1

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

样例输出 #1

2
5
-1
5
4

对于 的数据：，。