[Ynoi2013] 对数据结构的爱

题目描述

Nauuo 是一个喜欢编程的女孩子。有一天她在做一道题,要求计算一些数的和对一个数 $p$ 取模的结果。 她写出了如下的代码,然后获得了 WA 的评测结果。 ![](https://cdn.luogu.com.cn/upload/image_hosting/x18mqt81.png) 她很快发现了 bug——`ModAdd` 函数只对 $[0,p)$ 中的数起作用,但是这个问题中的数有可能不在这个范围之内。她对这个错误的函数很好奇,所以她想知道它的运行结果。 然而,原来的代码运行得太慢了,所以她来找你求助。 给定数组 $a_1,a_2,…a_n$ 和一个数 $p$,有 $m$ 个询问,每次给定两个数 $l$ 和 $r$,你需要计算函数 `Sum(a,l,r,p)` 的返回值。函数 `Sum` 的定义在上面的伪代码中已经给出。 注意,在上面的代码中,整数不会越界。

输入输出格式

输入格式


第一行三个整数 $n$,$m$,$p$,分别代表数组的长度,询问的个数和模数。注意模数只在 `ModAdd` 中用到。 第二行包含 $n$ 个整数 $a_1,a_2,…a_n$,代表给定的数组。 接下来的 $m$ 行,每行两个整数 $l$ 和 $r$,你需要计算 `Sum(a,l,r,x,p)`。 **本题强制在线,所有输入的 $l,r,x$ 均需要异或 $lastans$,其定义为上一次询问操作得到的答案对 $n$ 取模后的值,若答案为负数,则需要取模为正数,若之前没有询问操作,则为 $0$。**

输出格式


按顺序输出 $m$ 个整数,每个一行,代表询问的答案。

输入输出样例

输入样例 #1

4 5 6
7 2 -3 17
2 3 1
1 3 3
0 3 0
2 4 2
4 4 0

输出样例 #1

0
-3
4
12
11

说明

Idea:rushcheyo&nzhtl1477,Solution:ccz181078,Code:rushcheyo&ccz181078,Data:rushcheyo&nzhtl1477 对于 $100\%$ 的数据,$1\le n\le10^6$,$1\le m\le2\times 10^5$,$1\le p\le10^9$,$-10^9\le a_i\le10^9$,$1\le l\le r\le n$,$0\le x\le p-1$。