题目描述
Nauuo 是一个喜欢编程的女孩子。有一天她在做一道题，要求计算一些数的和对一个数 $p$ 取模的结果。
她写出了如下的代码，然后获得了 WA 的评测结果。
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$ 个整数，每个一行，代表询问的答案。
样例 #1
样例输入 #1
4 5 6 7 2 -3 17 2 3 1 3 1 2 2 4 4 4
样例输出 #1
-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$。