//太困难了 //喵喵喵 //Cidoai出版 #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; inline ll read(){ ll x=0; int f=0,ch=0; while(ch<48||ch>57) f=(ch=='-'),ch=getchar(); while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar(); return f?-x:x; } inline void write(ll x,char end='\n'){ if(x==0){ putchar('0'); putchar(end); return; } if(x<0) putchar('-'),x=-x; int ch[70]={0},cnt=0; while(x){ ch[cnt++]=(int)(x%10); x/=10; } while(cnt--) putchar(ch[cnt]+48); putchar(end); } //我们设f(x)=ModAdd(x,0,p),g(x,n)=f^(n)(x) //x-f(x)=0或p //如果|x-y|<p，那么|f(x)-f(y)|<p,|g(x,n)-g(y,n)|<p //x-g(x)=(0~n)p //因此可得x-g(x)是一个递增函数 //我们可以把x-g(x)存入到线段树中,第dep层存x-g(x,2^dep) //用upper_bound的O(log(n))的时间复杂度找出一个区间中+sum后需要-p的和个数 const ll inf=-1e17; ll p; inline void addmod(ll &x,int y){(x+=y)>=p&&(x-=p);} const int N=1e6+5; int n,m; int a[N]; //线段树分层存储 //只有分层后才能满足递增序列的要求，可以进行upper_bound的操作 ll s[N<<2],tree[22][N]; inline void build(int x,int l,int r,int dep){ if(l==r){ s[x]=a[l]; tree[dep][l]=-s[x]+p; return; } int mid=(l+r)>>1; build(x<<1,l,mid,dep+1); build(x<<1|1,mid+1,r,dep+1); s[x]=s[x<<1]+s[x<<1|1]; //下面这一大段是为了找出这个区间中需要减去p的数的个数 int i=l-1,j=mid,k=l-1; while(i<=mid){ ll t=p*(i-l+1); ll g0=tree[dep+1][i]; ll g1=tree[dep+1][i+1]; ll s1=s[x<<1]; while(j>mid&&i>=l&&tree[dep+1][j]>g0+s1-t) --j; while(j<=r&&(i==mid||j==mid||tree[dep+1][j]<g1+s1-t)){ ll l0=tree[dep+1][j]; if(i+j-mid>k){ k=i+j-mid; tree[dep][k]=max((i==l-1)?inf:g0,(j==mid)?inf:(l0-s1+t)); } ++j; } --j; ++i; } } inline ll query(int x,int l,int r,int dep,int ql,int qr,ll sum){ if(ql<=l&&r<=qr){ int pos=upper_bound(tree[dep]+l,tree[dep]+r+1,sum)-tree[dep]-l; return sum+s[x]-p*pos; } int mid=(l+r)>>1; if(ql<=mid) sum=query(x<<1,l,mid,dep+1,ql,qr,sum); if(mid<qr) sum=query(x<<1|1,mid+1,r,dep+1,ql,qr,sum); return sum; } //总时间复杂度是O(nlog^2(n))级别的……吧？ //很玄学，上限是4*10^8，希望能过？ //这场很厉害，T2T4可做，T1T3却没正解思路 int main(){ n=read(),m=read(),p=read(); for(int i=1;i<=n;++i) a[i]=read(); build(1,1,n,0); while(m--){ int l=read(),r=read(); write(query(1,1,n,0,l,r,0)); } return 0; }