题目描述

Nauuo 是一个喜欢编程的女孩子。有一天她在做一道题，要求计算一些数的和对一个数 $p$ 取模的结果。

她写出了如下的代码，然后获得了 WA 的评测结果。

她很快发现了 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,p)。

输出格式

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

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

-1
0
3
10
11

提示

Idea：rushcheyo，Solution：ccz181078，Code：rushcheyo&ccz181078，Data：rushcheyo

对于 $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$。