#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 10;
ll mod;
ll a[maxn];
int n;
pii q[maxn];
vector<int> bounds[maxn*4];
ll ans[maxn];
void select(int i,int id,int l,int r)
{
int mid = l+r>>1;
if(q[id].fi <= mid && q[id].se > mid)
{
bounds[i].pb(id);
return;
}
int ii = i + i;
if(q[id].se <= mid) select(ii,id,l,mid);
else select(ii+1,id,mid+1,r);
}
vector<pii> s[maxn];
struct bruh
{
ll sum,cnt,len;
};
vector<pii> st;
vector<bruh>v;
void solve(int id,int l,int r)
{
if(l==r)return;
int mid = l+r>>1,ii = id + id;
for(int i = l;i<=r;i++) s[i].clear();
for(int i : bounds[id]) s[q[i].se].pb(mk(q[i].fi,i));
ll C = INT_MIN,D,total,cnt = 0;
st.clear();
for(int i = mid + 1;i<=r;i++)
{
ll d = a[i] % mod;
ll c = a[i] / mod;
if(C==INT_MIN)
{
st.pb(mk(i,c));
total = a[i];
}
else
{
bool ch = (d < D);
ll tmp = C - (c - ch);
if(tmp < 0)
{
st.pb(mk(i,-tmp));
}
else
{
while(st.size() && tmp)
{
if(st.size()==1)
{
total -= tmp * mod;
cnt += tmp * (i - st.back().fi);
break;
}
else
{
if(tmp >= st.back().se)
{
tmp -= st.back().se;
cnt += st.back().se * (i - st.back().fi);
st.pop_back();
}
else
{
st.back().se -= tmp;
cnt += tmp * (i - st.back().fi);
break;
}
}
}
}
}
// cout<<mid<<' '<<i<<' '<<total<<'\n';
for(pii k : s[i])
{
s[k.fi].pb(mk(total,k.se));
ans[k.se] += cnt;
// cout<<i<<' '<<mid<<' '<<k.se<<' '<<k.fi<<' '<<total<<'\n';
}
C = c,D = d;
}
C = INT_MIN;
v.clear();
v.pb({0,0,0});
cnt = 0;
for(int i = mid;i>=l;i--)
{
ll d = a[i] % mod;
ll c = a[i] / mod;
// cout<<mid<<' '<<i<<' ';
if(C==INT_MIN)
{
v.pb({(mid-i+1) * c,c,mid-i+1});
}
else
{
bool ch = (D < d);
ll tmp = (C - ch);
// cout<<c<<' '<<tmp<<'!'<<' ';
if(c >= tmp)
{
cnt += c-tmp;
c = tmp;
tmp = 0;
v.pop_back();
}
else
{
tmp -= c;
v.back().sum -= (C-tmp) * (mid - i);
v.back().cnt -= C-tmp;
}
v.pb({(mid-i+1) * c + v.back().sum, c + v.back().cnt,mid-i+1});
}
// cout<<c<<'\n';
C = c,D = d;
for(pii k : s[i])
{
if(k.fi < 0||c<0)
{
ans[k.se] = -1;
continue;
}
ll tmp = (a[mid] - k.fi + mod-1) / mod;
// cout<<i<<' '<<mid<<' '<<k.se<<' '<<k.fi<<' '<<tmp<<'\n';
ans[k.se] += cnt;
if(tmp > 0)
{
int L = 1,R = v.size() - 1,M;
while(L<R)
{
M = (L+R+1)>>1;
if(v[M-1].cnt <= tmp) L = M;
else R = M-1;
}
// L = R;
tmp -= v[L-1].cnt;
ans[k.se] += v[L-1].sum;
ans[k.se] += v[L].len * tmp;
// cout<<v[L-1].sum<<' '<<v[L].len<<' '<<tmp<<'\n';
if(L==v.size()-1 && c<tmp) ans[k.se] = -1;
}
}
}
solve(ii,l,mid);
solve(ii+1,mid+1,r);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("a.inp","r"))
{
freopen("a.inp","r",stdin);
freopen("a.out","w",stdout);
}
cin>>n>>mod;
for(int i = 1;i<=n;i++) cin>>a[i];
int m;
cin>>m;
for(int i = 1;i<=m;i++)
{
cin>>q[i].fi>>q[i].se;
if(q[i].fi==q[i].se)continue;
select(1,i,1,n);
}
solve(1,1,n);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}
