#include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int f=1,x=0; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') f*=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } const int N=1e6+7; int n,m,a[N],p; bool tsxz[4]; signed main() { n=read(); m=read(); p=read(); tsxz[0]=tsxz[1]=tsxz[2]=tsxz[3]=true; for(int i=1;i<=n;i++) { a[i]=read(); if(a[i]>=p||a[i]<0) tsxz[0]=false; if(a[i]<p) tsxz[1]=false; if(i!=1&&a[i]<a[i-1]) tsxz[2]=false; if(i!=1&&a[i]>a[i-1]) tsxz[3]=false; } if(tsxz[0]) { for(int i=1;i<=n;i++) { a[i]+=a[i-1]; } while(m--) { int l=read(),r=read(); if(l>r) printf("0\n"); else printf("%lld\n",(a[r]-a[l-1])%p); } return 0; } if(tsxz[1]) { for(int i=1;i<=n;i++) { a[i]+=a[i-1]; } while(m--) { int l=read(),r=read(); if(l>r) printf("0\n"); else printf("%lld\n",a[r]-a[l-1]-p*(r-l+1)); } return 0; } if(tsxz[2]) { int now=n,wei=n+1; for(int i=1;i<=n;i++) { if(a[i]>0) { now=i-1; break; } } for(int i=now+1;i<=n;i++) { if(a[i]>=p) { wei=i; break; } } for(int i=1;i<=n;i++) { a[i]+=a[i-1]; } while(m--) { int l=read(),r=read(); if(l>r) { printf("0\n"); continue; } if(r<=now) { printf("%lld\n",a[r]-a[l-1]); } else if(l>now) { if(r<wei) { printf("%lld\n",(a[r]-a[l-1])%p); } else if(l>=wei) { printf("%lld\n",a[r]-a[l-1]-(r-l+1)*p); } else { printf("%lld\n",(a[wei-1]-a[l-1])%p+a[r]-a[wei-1]-(r-wei+1)*p); } } else { int lsum=a[now]-a[l-1]; int ll=now+1,rr=n,nd=n+1; while(ll<=rr) { // cout<<'?'; int mid=(ll+rr)/2; if(a[mid]-a[now]+lsum>=0) { nd=mid; rr=mid-1; } else ll=mid+1; } int sum=a[nd]-a[now]+lsum; if(nd>r) { printf("%lld\n",a[r]-a[l-1]); } else if(r<wei) { printf("%lld\n",(a[r]-a[l-1])%p); } else if(nd<wei) { printf("%lld\n",(a[wei-1]-a[l-1])%p+a[r]-a[wei-1]-(r-wei+1)*p); } else { if(sum>p) sum-=p; printf("%lld\n",sum+a[r]-a[nd]-(r-nd)*p); } } } return 0; } if(tsxz[3]) { int now=n,wei=n+1; for(int i=1;i<=n;i++) { if(a[i]<0) { now=i-1; break; } } for(int i=1;i<=n;i++) { a[i]+=a[i-1]; } while(m--) { int l=read(),r=read(); if(l>r) { printf("0\n"); continue; } if(r<=now) { printf("%lld\n",max((a[r]-a[l-1])%p,a[r]-a[l-1]-(r-l+1)*p)); } else if(l>now) { printf("%lld\n",a[r]-a[l-1]); } else { int lsum=max((a[now]-a[l-1])%p,a[now]-a[l-1]-(now-l+1)*p); int ll=now,rr=n+1,nd=n+1; while(ll<=rr) { int mid=(ll+rr)/2; if(lsum+a[mid]-a[now]-p*((mid-now))<p) { nd=mid; rr=mid-1; } else ll=mid+1; } if(r<=nd) printf("%lld\n",lsum+a[r]-a[now]-p*((r-now))); else printf("%lld\n",lsum+a[r]-a[now]-p*(nd-now)); } } return 0; } return 0; }