#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=1e6+10;
const ll INF=1e14;
int n,m,q,t[MAXN],top,s[MAXN],f[20][MAXN];
ll T,w[MAXN],h[20][MAXN],g[20][MAXN];__int128 S,ans;
inline ll Q(int l,int r)
{
    int t=__lg(r-l+1);
    return max(h[t][r],h[t][l+(1<<t)-1]);
}
inline void calc(int l,int r,__int128 &now,int del=0)
{
    if(l>r) return ;
    if(Q(l,r)+del<=now){ans+=(r-l+1)*now;return ;}
    int L=l,R=r;while(L<R)
        {int m=(L+R)>>1;(Q(l,m)+del>now)?R=m:L=m+1;}
    ans+=(L-l)*now;for(int i=19;~i;--i)
        if(f[i][L]&&f[i][L]<=r) ans+=g[i][L],L=f[i][L];
    now=w[L]+del,ans+=(r-L+1)*now;return ;
}
inline void calc(ll num,__int128 &now)
    {if(num>now) now=num;ans+=now;}
inline void write(__int128 num)
{
    if(!num) return ;write(num/10);
    cout<<(int)(num%10);return ;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m>>q>>T;
    for(int i=1;i<=n;++i)
    {
        cin>>t[i],S+=(h[0][i]=w[i]=t[i]-i*T);
        for(int j=1;j<=__lg(i);++j)
            h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
    }
    for(int i=n;i;--i)
    {
        while(top&&w[s[top]]<=w[i]) --top;
        g[0][i]=w[i]*((f[0][i]=s[top])-i),s[++top]=i;
        for(int j=1;j<20;++j)
            f[j][i]=f[j-1][f[j-1][i]],
            g[j][i]=g[j-1][i]+g[j-1][f[j-1][i]];
    }
    for(int x,y;q;--q)
    {
        cin>>x>>y;__int128 now=-INF;ans=0;
        int k=upper_bound(t+1,t+1+n,y)-t;
        if(x<=k)
        {
            calc(1,x-1,now);
            calc(x+1,k-1,now,T);
            calc(y-1ll*(k-1)*T,now);
            calc(k,n,now);
        }
        else
        {
            calc(1,k-1,now);
            calc(y-1ll*(k-1)*T,now);
            calc(k,x-1,now,-T);
            calc(x+1,n,now);
        }
        write(ans-(S-t[x]+y)),cout<<'\n';
    }
}