#include<bits/stdc++.h> using namespace std; #define N 1000005 #define SN 1005 #define M 200005 #define ll long long int unit; int a[N],ap[N],id[N]; ll sum[N],sum2[N],p; int lb[SN],bpl[SN],nb[SN],fr[SN],fl[SN]; inline ll qry(int l,int r){ ll res=0; if(r<l)return 0; if(id[l]==id[r]){ for(int i=l;i<=r;i++){ res+=a[i]; if(res>p)res-=p; } return res; } ll lap=0,cnp=0,pl=r+1; for(int i=r;id[i]==id[r];i--){ lap+=ap[i]; if(lap>=pl-i){ cnp+=lap; lap=0; pl=i; } } for(int i=id[r]-1;i>id[l];i--){ lap+=lb[i]; if(lap>=pl-bpl[i]){ pl=bpl[i]; cnp+=lap; lap=0; } lap+=nb[i]; } for(int i=fr[id[l]];i>=l;i--){ lap+=ap[i]; if(lap>=pl-i){ cnp+=lap; lap=0; pl=i; } } res=sum[r]-sum[pl-1]+(sum2[pl-1]+p-sum2[l-1])%p+(cnp-(r-pl+1))*p; return res; } int main(){ int n,m; scanf("%d%d%lld",&n,&m,&p); int len=0,cnb=1; fl[1]=1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]%p,sum2[i]=(sum2[i-1]+a[i])%p,ap[i]=a[i]/p; len++; id[i]=cnb; if(len*len>=n)fr[cnb]=i,cnb++,len=0,fl[cnb]=i+1; } fr[cnb]=n,len=0; for(int i=1;i<=cnb;i++){ int lap=0,cnp=0,pl=fr[i]+1; for(int j=fr[i];j>=fl[i];j--){ lap+=ap[j]; if(lap>=pl-j){ cnp+=lap; lap=0; pl=j; } } lb[i]=cnp,nb[i]=lap,bpl[i]=pl; } while(m--){ int l,r; scanf("%d%d",&l,&r); printf("%lld\n",qry(l,r)); } return 0; } /* hack 20 2 31 33 16 21 45 1 53 34 92 95 64 39 9 26 45 74 55 10 18 24 8 11 18 5 20 做法假了 */