题目描述

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

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

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

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

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

输入格式

第一行两个正整数 $n,m,t$。$n$ 表示猪圈数，$m$ 表示询问数，$t=0$ 表示方老师没有对询问进行加密，$t=1$ 表示方老师对询问进行了加密，解密方法如下：

$$l'=(l'\oplus |lastans|)\mod n+1 \\ r'=(r'\oplus |lastans|)\mod n+1 \\ l=\min(l',r'),r=\max(l',r') $$

其中 $\oplus$ 表示异或操作，$lastans$ 表示上一次询问的答案，对于第一次询问，$lastans=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

数据规模与约定

对于 $100\%$ 的数据：$N,M\le 5\times 10^5$，$|x_i|\le 8\times 10^6$。