#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=1e6+10;
const ll INF=1e18;
int n,m,q,t[MAXN],top,s[MAXN];
ll T;__int128 S,now,ans;
struct node
{
    int I,n;vector <int> t,f[20];
    vector <ll> w,h[20],g[20];
    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,int del=0)
    {
        l=(l-I)/m+((l-I)%m!=0),r=(r-I)/m;
        if(l>r) return ;del=-del*T;
        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;int tmp=L;
        for(int i=__lg(n);~i;--i)
            if(f[i][L]&&f[i][L]<=r) ans+=g[i][L],L=f[i][L];
        ans+=(L-tmp)*del;
        now=w[L]+del,ans+=(r-L+1)*now;return ;
    }
    inline void init()
    {
        n=t.size(),top=0,w.resize(n);
        for(int i=0;i<=__lg(n);++i)
            f[i].resize(n),g[i].resize(n),h[i].resize(n);
        for(int i=0;i<n;++i)
        {
            S+=(h[0][i]=w[i]=t[i]-i*T);
            for(int j=1;j<=__lg(i+1);++j)
                h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
        }
        for(int i=n-1;~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;f[j-1][i];++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]];
        }
    }
}o[5];
inline void calc(ll num)
    {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("shuju.txt","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=0;i<m;++i) o[i].I=i;
    for(int i=0;i<n;++i)
        cin>>t[i],o[i%m].t.push_back(t[i]);
    for(int i=0;i<m;++i) o[i].init();
    for(int x,y;q;--q)
    {
        cin>>x>>y;--x,ans=0;
        int k=upper_bound(t,t+n,y)-t-1;
        if(x==k)
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,x-1);
                if(x%m==i) calc(y-1ll*(x/m)*T);
                o[i].calc(x+1,n-1);
            }
        }
        else if(x<k)
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,x-1);
                o[(i+1)%m].calc(x+1,k-1,-1);
                if((k-1)%m==i) calc(y-1ll*((k-1)/m)*T);
                o[i].calc(k,n-1);
            }
        }
        else
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,k-1);
                if(k%m==i) calc(y-1ll*(k/m)*T);
                o[(i+m-1)%m].calc(k,x-1,+1);
                o[i].calc(x+1,n-1);
            }
        }
        write(ans-(S-t[x]+y)),cout<<'\n';
    }
    return 0;
}