#include<bits/stdc++.h> using namespace std; char buf1[2097152],*ip1=buf1,*ip2=buf1; inline int getc(){ return ip1==ip2&&(ip2=(ip1=buf1)+fread(buf1,1,2097152,stdin),ip1==ip2)?EOF:*ip1++; } template<typename T>void in(T &a) { T ans=0; bool f=0; char c=getc(); for(;c<'0'||c>'9';c=getc())if(c=='-')f=1; for(;c>='0'&&c<='9';c=getc())ans=ans*10+c-'0'; a=(f?-ans:ans); } template<typename T,typename... Args>void in(T &a,Args&...args) { in(a),in(args...); } int n,m; long long p,a[1000005],v[4000005]; vector<long long>c[4000005]; void pushup(int pos,int nl,int nr){ v[pos]=v[pos<<1]+v[pos<<1|1]; int mid=(nl+nr)>>1; for(int l=0,r=0;l<=mid-nl+1;l++){ if(r==nr-mid+1)r--; while(1){ c[pos][l+r]=min(c[pos][l+r],max(c[pos<<1][l],c[pos<<1|1][r]+l*p-v[pos<<1])); if(r==nr-mid||c[pos<<1|1][r+1]>c[pos<<1][l+1]-l*p+v[pos<<1]-1)break; r++; } } } void build(int pos,int nl,int nr,long long a[]){ c[pos].push_back(-0x3f3f3f3f3f3f3f3f); for(int i=1;i<=nr-nl+2;i++)c[pos].push_back(0x3f3f3f3f3f3f3f3f); if(nl==nr)v[pos]=a[nl],c[pos][1]=p-a[nl]; else{ int mid=(nl+nr)>>1; build(pos<<1,nl,mid,a),build(pos<<1|1,mid+1,nr,a),pushup(pos,nl,nr); } } long long query(int pos,int nl,int nr,int gl,int gr,long long ans=0){ if(gl<=nl&&nr<=gr)return ans+v[pos]-(upper_bound(c[pos].begin(),c[pos].end(),ans)-c[pos].begin()-1)*p; int mid=(nl+nr)>>1; if(gl<=mid)ans=query(pos<<1,nl,mid,gl,gr,ans); if(gr>mid)ans=query(pos<<1|1,mid+1,nr,gl,gr,ans); return ans; } int main(){ in(n,m,p); for(int i=1;i<=n;i++)in(a[i]); build(1,1,n,a); for(int i=1,l,r;i<=m;i++)in(l,r),cout<<query(1,1,n,l,r)<<'\n'; return 0; }