#include<bits/stdc++.h>//60pts using namespace std; int n,m,p,a[1000010]; int num[1000010]; int cnt=1,lst[1000010]; int t[4000010]; int ls(int x){return x<<1;} int rs(int x){return x<<1|1;} void up(int x) { t[x]=t[ls(x)]+t[rs(x)]; } void build(int x,int l,int r) { if(l==r) { t[x]=a[l]; return ; } int mid=(l+r)>>1; build(ls(x),l,mid); build(rs(x),mid+1,r); up(x); } int ask(int x,int l,int r,int L,int R) { if(L<=l&&r<=R) { return t[x]; } int ans=0,mid=(l+r)>>1; if(L<=mid) ans+=ask(ls(x),l,mid,L,R); if(mid<R) ans+=ask(rs(x),mid+1,r,L,R); return ans; } int main() { cin>>n>>m>>p; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); for(int i=1;i<=n;i++) { num[i]=cnt; if(a[i]>=p&&a[i+1]<p) lst[cnt++]=i; if(a[i]<p&&a[i+1]>=p) lst[cnt++]=i; } lst[cnt]=n; while(m--) { int l,r; cin>>l>>r; int f=0; if(a[l]>=p) f=1; int ans=0; int res; while(l<=r) { res=ask(1,1,n,l,min(r,lst[num[l]])); if(f==1) { res-=p*(min(lst[num[l]],r)-l+1); ans+=res; } else { int num1=(ans+res)/p; // cout<<ans<<" "<<res<<" "<<num1<<endl; ans=(ans+res)-p*min(num1,min(lst[num[l]],r)-l+1); } f=abs(f-1); l=lst[num[l]]+1; // cout<<ans<<endl; } cout<<ans<<endl; } return 0; } /* 10 1 27284 25724 15721 26342 29973 29764 23666 2532 18956 205 17611 3 6 */