D. 早凉的程序2

早凉在学习取模运算之后，写了一个“计算模 p 意义下的区间和”的程序：

#include<bits/stdc++.h>
using namespace std;
int a[1000006],n,m,p;
int main() {
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1; i<=n; ++i) 
		scanf("%d",&a[i]);
	for(int i=1; i<=m; ++i) {
		int l,r;
		scanf("%d%d",&l,&r);
		long long ans=0;
		for(int j=l; j<=r; ++j) {
			ans+=a[j];
			if(ans>=p) ans-=p;
		}
		printf("%lld\n",ans);
	}
	return 0;
} 

显然这个程序在 0\leq a_i < p 时才能保证正确性。

即使如此，早凉仍然想要知道上述程序的输出。

也就是说，早凉会给你输入，你需要写一个效率更高的程序来实现和原程序一样的功能。

早凉的程序在 1576\text{ms} 内就运行完了，你的程序一定能更快吧。

第一行三个正整数 n,m,p。

第二行 n 个整数，第 i 个为 a_i。

第三至 m+2 行，每行两个数 l,r。

需要和上述程序的输出完全一致。

1\leq n\leq 10^6,1\leq m\leq2\times10^5,-10^9\leq a_i\leq 10^9,1\leq p\leq 10^9。

特殊性质 A: 对于任意正整数 i(1\leq i\leq n)，0\leq a_i < p。

特殊性质 B: 对于任意正整数 i(1\leq i\leq n)，a_i \geq p。

特殊性质 C: 对于任意正整数 i(1\leq i < n)，a_i\leq a_{i+1}。

特殊性质 D: 对于任意正整数 i(1\leq i < n)，a_i\geq a_{i+1}。