#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 p,a[N],n,m; struct dian { int l,r,siz; int sum; vector<int>c; }d[N<<2]; void build(int rt,int l,int r) { d[rt].l=l; d[rt].r=r; d[rt].siz=r-l+1; for(int i=0;i<=r-l+3;i++) d[rt].c.push_back(1e18); if(l==r) { d[rt].sum=a[l]; d[rt].c[0]=-1e18; d[rt].c[1]=p-a[l]; return; } int mid=(l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); d[rt].sum=d[rt<<1].sum+d[rt<<1|1].sum; for(int x=0,k=0;x<=d[rt<<1].siz;x++) { if(k>d[rt<<1|1].siz) --k; for(;k<=d[rt<<1|1].siz;++k) { if(d[rt<<1].c[x+1]-1+d[rt<<1].sum-x*1ll*p<d[rt<<1|1].c[k]) { if(k) k--; break; } d[rt].c[x+k]=min(d[rt].c[x+k],max(d[rt<<1].c[x],d[rt<<1|1].c[k]-d[rt<<1].sum+x*p)); } } } int ans=0; void query(int rt,int l,int r) { if(l<=d[rt].l&&d[rt].r<=r) { // cout<<d[rt].l<<' '<<d[rt].r<<' '<<upper_bound(d[rt].c.begin(),d[rt].c.end(),ans)-d[rt].c.begin()-1<<endl; ans+=d[rt].sum-p*(upper_bound(d[rt].c.begin(),d[rt].c.end(),ans)-d[rt].c.begin()-1); return; } int mid=(d[rt].l+d[rt].r)/2; if(l<=mid)query(rt<<1,l,r); if(r>mid)query(rt<<1|1,l,r); } signed main() { n=read(); m=read(); p=read(); for(int i=1;i<=n;i++) { a[i]=read(); } build(1,1,n); for(int i=1;i<=m;i++) { ans=0; int l,r; l=read(); r=read(); query(1,l,r); printf("%lld\n",ans); } return 0; }