#include <bits/stdc++.h> using namespace std; const int maxn=100010; typedef long long ll; ll t[maxn],a[maxn],n,m,p,minn,maxx,num[maxn],pos,pos1,num1[maxn],num2[maxn],l,r; bool flag1,flag2; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>p; maxx=-1,minn=LONG_LONG_MAX,flag1=1,flag2=1; for(int i=1; i<=n; i++) { cin>>a[i]; minn=min(minn,a[i]),maxx=max(maxx,a[i]); num[i]=num[i-1]+a[i]; if(a[i]>=p) pos=i; if(a[i]<p) pos1=i; if(a[i-1]>a[i]) flag1=0; else if(a[i-1]<a[i]) flag2=0; } if((maxx<p && minn>=0) || minn>=p) { while(m--) { cin>>l>>r; if(maxx<p) cout<<(num[r]-num[l-1])%p<<'\n'; else cout<<(num[r]-num[l-1])-(r-l+1)*p<<'\n'; } return 0; } if(flag1) { pos=pos1+1; while(m--) { cin>>l>>r; if(r<pos) cout<<(num[r]-num[l-1])%p<<'\n'; else if(l>pos) cout<<(num[r]-num[l-1])-(r-l+1)*p<<'\n'; else { ll ans=0; ans+=(num[pos-1]-num[l-1])%p; ans+=(num[r]-num[pos-1])-(r-pos+1)*p; cout<<ans<<'\n'; } } return 0; } if(flag2) { while(m--) { cin>>l>>r; if(r<pos) cout<<(num[r]-num[l-1])-(r-l+1)*p<<'\n'; else if(l>pos) cout<<(num[r]-num[l-1])%p<<'\n'; else { ll ans=0; ans+=(num[pos-1]-num[l-1])%p; ans+=(num[r]-num[pos-1])-(r-pos+1)*p; cout<<ans<<'\n'; } } return 0; } sort(a+1,a+n+1); for(int i=1; i<=n; i++) { num[i]=num[i-1]+a[i]; if(a[i]<p) pos1=i; } pos=pos1+1; while(m--) { cin>>l>>r; if(r<pos) cout<<(num[r]-num[l-1])-(r-l+1)*p<<'\n'; else if(l>pos) cout<<(num[r]-num[l-1])%p<<'\n'; else { ll ans=0; ans+=(num[pos-1]-num[l-1])%p; ans+=(num[r]-num[pos-1])-(r-pos+1)*p; cout<<ans<<'\n'; } } return 0; }