//chockolateman
#include<bits/stdc++.h>
using namespace std;
int N,Q,a[500005],nxt[500005],status[500005],lazy[2000005]; // status is the first even position you found this mod
long long K,preff[500005];
vector<long long> int_mod;
void propagate(int v,int start,int end);
void update(int l,int r,int val,int v = 1,int start = 1,int end = N)
{
if(start==l && end==r)
{
lazy[v] = val;
if(start==end)
status[start] = val;
return;
}
propagate(v,start,end);
int mid = (start + end)/2;
if(r <= mid)
update(l,r,val,2*v,start,mid);
else if(l > mid)
update(l,r,val,2*v+1,mid+1,end);
else
{
update(l,mid,val,2*v,start,mid);
update(mid+1,r,val,2*v+1,mid+1,end);
}
}
void propagate(int v,int start,int end)
{
if(lazy[v])
{
int mid = (start + end)/2;
update(start,mid,lazy[v],2*v,start,mid);
update(mid+1,end,lazy[v],2*v+1,mid+1,end);
lazy[v] = 0;
}
}
void push(int pos,int v = 1,int start = 1,int end = N)
{
if(start==end)
return;
propagate(v,start,end);
int mid = (start + end)/2;
if(pos <= mid)
push(pos,2*v,start,mid);
else
push(pos,2*v+1,mid+1,end);
}
void update_seg(long long start,long long end,int val)
{
int l = lower_bound(int_mod.begin(),int_mod.end(),start) - int_mod.begin() + 1;
int r = upper_bound(int_mod.begin(),int_mod.end(),end) - int_mod.begin();
if(l <= r)
update(l,r,val);
}
int main()
{
scanf("%d%d%lld",&N,&Q,&K);
for(int i = 1 ; i <= N ; i++)
{
scanf("%d",&a[i]);
if(i%2==1)
{
preff[i] = preff[i-1] + a[i];
int_mod.push_back(((preff[i-1]%K)+K)%K);
}
else
preff[i] = preff[i-1] - a[i];
}
sort(int_mod.begin(),int_mod.end());
int_mod.erase(unique(int_mod.begin(),int_mod.end()),int_mod.end());
update_seg(0,K-1,N+1);
for(int i = N ; i >= 1 ; i--)
{
if(i%2==1)
{
int pos = lower_bound(int_mod.begin(),int_mod.end(),((preff[i-1])%K+K)%K) - int_mod.begin() + 1;
push(pos);
nxt[i] = status[pos] - 1;
}
else
{
if(a[i] >= K)
update_seg(0,K-1,i);
else
{
long long end = ((preff[i-1]%K)+K)%K;
long long start = ((end - a[i] + 1)%K+K)%K;
if(start <= end)
update_seg(start,end,i);
else
{
update_seg(0,end,i);
update_seg(start,K-1,i);
}
}
}
}
for(int l,r,i = 1 ; i <= Q ; i++)
{
scanf("%d%d",&l,&r);
long long ans = 0;
int pos = l;
if(pos%2==0)
pos++;
while(pos <= r && nxt[pos] <= r)
{
ans += (preff[nxt[pos]] - preff[pos-1])/K;
pos = nxt[pos] + 2;
}
if(pos <= r)
ans += max(0ll,preff[r] - preff[pos-1])/K;
printf("%lld\n",ans);
}
return 0;
}
