#include<bits/stdc++.h> #define int long long using namespace std; const int Maxn=1e6+5; struct Node{ int l,r,sum; }t[Maxn<<2]; int a[Maxn],sum1[Maxn],sum2[Maxn],n,m,p; inline void PU(int pos) { t[pos].sum=(t[pos<<1].sum+t[pos<<1|1].sum); } inline void Build(int l,int r,int pos) { t[pos].l=l,t[pos].r=r; if(l==r) { t[pos].sum=a[l]; return ; } int mid=l+r>>1; Build(l,mid,pos<<1),Build(mid+1,r,pos<<1|1); PU(pos); } inline int Query(int l,int r,int pos) { if(r<l) return 0; if(l<=t[pos].l && t[pos].r<=r) return t[pos].sum; int mid=t[pos].l+t[pos].r>>1,ans=0; if(l<=mid) ans=(ans+Query(l,r,pos<<1)); if(mid<r) ans=(ans+Query(l,r,pos<<1|1)); return ans; } bool A=1,B=1,C=1,D=1; signed main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m>>p; //cout<<p<<'\n'; for(int i=1;i<=n;i++) { cin>>a[i]; sum1[i]=a[i]+sum1[i-1]; if(a[i]>=p || a[i]<0) A=0; if(a[i]<p) B=0; if(a[i]<a[i-1] && i>1) C=0; if(a[i]>a[i-1] && i>1) D=0; } for(int i=n;i>=1;i--) sum2[i]=sum2[i+1]+a[i]; //cout<<A<<' '<<B<<'\n'; Build(1,n,1); for(int i=1,l,r;i<=m;i++) { cin>>l>>r; if(A) cout<<Query(l,r,1)%p<<'\n'; else if(B) cout<<Query(l,r,1)-p*(r-l+1)<<'\n'; else if(C) { int pos=lower_bound(sum1+1+l,sum1+1+r,p+sum1[l-1])-sum1; //cout<<pos<<'\n'; cout<<Query(l,pos-1,1)%p+Query(pos,r,1)-(r-pos+1)*p<<'\n'; } else { long long ans=0; for(int j=l; j<=r; ++j) { ans+=a[j]; if(ans>=p) ans-=p; } cout<<ans<<'\n'; } } return 0; } /* 4 3 6 1 3 5 7 1 3 2 4 1 4 4 3 6 13 9 7 1 1 3 2 4 1 4 */