//t4 特殊性质ABCD 60分 /* a[i]<p:正常mod p意义下加法 a[i]>=p:每一步都减去p */ #include <bits/stdc++.h> using namespace std; long long p1,p2,p3,tmpi,qzh1[100005],mx,mn=2100000000,n,a[100005],maxn=-2100000000,minn=2100000000; long long m,p,x,y,a1,a2,a3; long long qs(long long l,long long r){ return qzh1[r]-qzh1[l-1]; } long long ef(){ long long an=-1,l=p1+1,r=n,mid=(l+r)/2,tmp9=qs(x,p1); while(r>l){ if((qs(p1+1,mid)+tmp9)>=0){ an=mid; r=mid-1; }else{ l=mid+1; } mid=(l+r)/2; } return an; } int main(){ cin>>n>>m>>p; for(long long i=1;i<=n;i++){ cin>>a[i]; mx=max(mx,a[i]); mn=min(mn,a[i]); } for(long long i=2;i<=n;i++){ maxn=max(maxn,a[i]-a[i-1]); minn=min(minn,a[i]-a[i-1]); } if(mx<p){ //A //bta(1,n,1); for(long long i=1;i<=n;i++)qzh1[i]=qzh1[i-1]+a[i]; for(long long i=1;i<=m;i++){ cin>>x>>y; //cout<<cha(x,y,1); tmpi=(qzh1[y]-qzh1[x-1])%p; if(x<=y)cout<<tmpi<<endl; else cout<<0<<endl; } }else if(mn>p){ //B for(long long i=1;i<=n;i++)qzh1[i]=qzh1[i-1]+a[i]; for(long long i=1;i<=m;i++){ cin>>x>>y; //cout<<cha(x,y,1); tmpi=(qzh1[y]-qzh1[x-1])-(y-x+1)*p; if(x<=y)cout<<tmpi<<endl; else cout<<0<<endl; } }else if(maxn<=0){ //D 单调递减 }else if(minn>=0){ //C 单调递增 p1=p2=100000000; for(long long i=1;i<=n;i++){ qzh1[i]=qzh1[i-1]+a[i]; } for(long long i=1;i<=n;i++){ if(a[i]>=0){ p1=i-1; break; } } for(long long i=p1;i<=n+2;i++){ if(a[i]>=p){ p2=i-1; break; } } if(a[1]>=0){ for(long long i=1;i<=m;i++){ cin>>x>>y; if(x>y)cout<<0<<endl; else if(y<=p2) cout<<(qzh1[y]-qzh1[x-1])%p<<endl; else if(x>p2)cout<<(qzh1[y]-qzh1[x-1])-(y-x+1)*p<<endl; else cout<<(qzh1[p2]-qzh1[x-1])%p+(qzh1[y]-qzh1[p2])-(y-p2)*p<<endl; } }else{ //cout<<"\na\na\na"; for(long long i=1;i<=m;i++){ cin>>x>>y; if(x>y)cout<<0<<endl; else if(x>p1){ if(y<=p2) cout<<(qzh1[y]-qzh1[x-1])%p; else if(x>p2)cout<<(qzh1[y]-qzh1[x-1])-(y-x+1)*p; else cout<<(qzh1[p2]-qzh1[x-1])%p+(qzh1[y]-qzh1[p2])-(y-p2)*p; }else{ long long tmp11=ef(); if(tmp11==-1||y<tmp11){ cout<<qs(x,y)<<endl; }else{ if(tmp11>=p2)cout<<qs(x,tmp11)-(long long)(qs(x,tmp11)>=p)*p+qs(tmp11+1,y)-p*(y-tmp11)<<endl; else if(y<=p2)cout<<(qs(x,tmp11)-(long long)(qs(x,tmp11)>=p)*p+(qs(tmp11+1,y)))%p<<endl; else cout<<(qs(x,tmp11)-(long long)(qs(x,tmp11)>=p)*p+(qs(tmp11+1,p2)))%p+qs(tmp11+1,y)-p*(y-tmp11)<<endl; } } } } } return 0; }