#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define fr(i,l,r) for (i=(l); i<=(r); i++)
#define rfr(i,l,r) for (i=(l); i>=(r); i--)
template<typename T>inline void read(T &n){
    T w=1; n=0; char ch=getchar();
    while (!isdigit(ch) && ch!=EOF){ if (ch=='-') w=-1; ch=getchar(); }
    while (isdigit(ch) && ch!=EOF){ n=(n<<3)+(n<<1)+(ch&15); ch=getchar(); }
    n*=w;
}
template<typename T>inline void write(T x){
    if (x==0){ putchar('0'); return ; }
    T tmp;
    if (x>0) tmp=x;
    else tmp=-x;
    if (x<0) putchar('-');
    char F[105];
    long long cnt=0;
    while (tmp){
        F[++cnt]=tmp%10+48;
        tmp/=10;
    }
    while (cnt) putchar(F[cnt--]);
}
#define Min(x,y) x = min(x,y)
#define Max(x,y) x = max(x,y)
//基础配置=================================================================================
const ll N = 1000005;
ll n,m,q,ts;
ll a[N];//原本的值
ll val[N];//限制的权值
ll calc_sum(ll l,ll r){
    if (l>r) return 0;
    return (r-l)/m + 1;
}
ll calc_pos(ll l,ll r){//[l,r]内最后一个和l%m同余的位置
    if (l>r) return l;
    else return l + (r-l)/m * m;
}
ll Nxt(ll p,ll op){//p后面第一个同余op的位置
    ll o = p%m;
    if (o==op) return p;
    if (o<op) return p+op-o;
    if (o>op) return p+(op+m)-o;
}
struct ST{//查询从某个点x开始，到r，最优一个前缀最小值和总贡献数(原序列意义下的总贡献数)
    ll lg;
    struct infor{
        ll p,v;
        infor(ll _p=0,ll _v=0){
            p = _p, v = _v;
        }
    };
    ll a[N];
    infor f[21][N];
    void init(){
        ll i,j;
        //找右边第一个%m同余的比a_i小的位置
        ll top = 0, q[N];
        fr(i,0,m-1){//%m同余
            top = 0;
            rfr(j,n,1){
                if (j%m!=i) continue;
                // printf("i = %lld , j = %lld\n",i,j);
                while (top>0 && a[j]<=a[q[top]]) top--;
                if (top==0) f[0][j] = infor( n+1 , a[j] * calc_sum(j,n) );
                else f[0][j] = infor( q[top] , a[j] * calc_sum(j,q[top]-1) );
                q[++top] = j;
            }
        }
        // fr(i,1,n) printf("f[0][%lld] : p = %lld , val = %lld\n",i,f[0][i].p,f[0][i].v);
        for (i=1; (1<<i)<=n; lg = i, i++)
            fr(j,1,n){
                ll x = f[i-1][j].p;
                if (x<=n){
                    f[i][j].p = f[i-1][x].p;
                    f[i][j].v = f[i-1][j].v + f[i-1][x].v;
                }
                else f[i][j] = f[i-1][j];
            }
    }
    pair<ll,ll> qry(ll x,ll r){//从x开始，以r为右端点
        // printf("\nqry %lld %lld\n",x,r);
        // make_pair( 区间内的贡献，最终的最小值 )
        ll i, ans = 0;
        rfr(i,lg,0){
            if (f[i][x].p<=r){
                ans += f[i][x].v;
                x = f[i][x].p;
            }
        }
        // printf("x = %lld\n",x);
        ans += a[x] * calc_sum(x,r);
        return make_pair(a[x],ans);
    }
    ll find(ll x,ll val){//从x开始第一个<val的位置
        if (a[x]<val) return x;
        for (ll i=lg; i>=0; i--){
            ll p = f[i][x].p;
            if (p<=n && a[p]>=val) x = p;
        }
        return f[0][x].p;
    }
}st;
pair<ll,ll> solve(ll l,ll r,ll pre,ll d){//意义见实现
    // printf("\n solve %lld ~ %lld , pre = %lld , delta = %lld\n",l,r,pre,d);
    if (l>r || l>n) return make_pair(pre,0);
    ll p = st.find(l,pre-d);
    // printf("p = %lld\n",p);
    if (p>r){
        // printf("return %lld %lld\n",pre,calc_sum(l,r)*pre);
        return make_pair(pre,calc_sum(l,r)*pre);
    }
    pair<ll,ll> v = st.qry(p,r);
    ll ans = calc_sum(l,p-1)*pre + (v.second+calc_sum(p,r)*d);
    // printf("return %lld %lld\n",v.first+d,ans);
    return make_pair(v.first+d,ans);
}
ll find_l(ll tms){//<=tms的最后一个位置
    ll l = 1, r = n, mid = (l+r)>>1;
    while (l<=r){
        mid = (l+r)>>1;
        if (a[mid]<=tms) l = mid+1;
        else r = mid-1;
    }
    return r;
}
pair<ll,ll> push(pair<ll,ll> p,ll v){
    Min(p.first,v); p.second += p.first;
    return p;
}
ll solve1(ll x,ll y,ll nwv){//向后放
    // printf("solve1 %lld --> %lld : nwv = %lld\n",x,y,nwv);
    ll i, ans = 0;
    fr(i,1,min(n,m)){//起点
        // printf("\n\n\n\n\n i = %lld\n",i);
        pair<ll,ll> v = solve(i,x-1,inf,0); ans += v.second;
        // printf("v1 : %lld %lld\n",v.first,v.second);
        ll p = Nxt(x,i%m);
        v = solve(Nxt(x,i%m)+1,y,v.first,-ts);// ans += v.second;
        // p = calc_pos(y,i%m);
        if (i%m==y%m) v = push(v,nwv);
        // printf("v2 : %lld %lld\n",v.first,v.second);
        ans += v.second;
        v = solve(Nxt(y+1,i%m),n,v.first,0); ans += v.second;
    }
    return ans;
}
ll solve2(ll x,ll nwv){//位置不变
    ll i, ans = 0;
    fr(i,1,min(n,m)){
        if (x%m!=i%m)//本来的值不用变
            ans += st.qry(i,n).second;
        else{
            pair<ll,ll> p;
            p = push( solve(i,x-1,inf,0) , nwv );
            ans += p.second + solve(x+m,n,p.first,0).second;
        }
    }
    return ans;
}
ll solve3(ll x,ll y,ll nwv){//向前放
    ll i, ans = 0;
    fr(i,1,min(n,m)){
        pair<ll,ll> v = solve(i,y-1,inf,0);
        // ll p = calc_pos(i,y);
        if (i%m==y%m) v = push(v,nwv);
        ans += v.second;
        v = solve(Nxt(y+1,i)-1,x-1,v.first,ts); ans += v.second;
        // p = calc_pos(p+m,x-1)+m;
        v = solve(Nxt(x+1,i),n,v.first,ts); ans += v.second;
    }
    return ans;
}
int main(){
	// freopen("a.in","r",stdin);
//	freopen(".out","w",stdout);
    ll i,j;
    read(n); read(m); read(q); read(ts);
    fr(i,1,n) read(a[i]), val[i] = i*ts - a[i];
    // printf("___\n");
    fr(i,1,n) st.a[i] = val[i]; st.init();//预处理
    // printf("___\n");
    ll all = 0; fr(i,1,n) all = all+i*ts-a[i];
    while (q--){
        ll x,y,t;
        read(x); read(t);
        ll p = find_l(t);
        if (p>=x) y = p; else y = p+1;
        // printf("x = %lld , y = %lld\n",x,y);
        ll ans = 0;
        if (x< y) ans = solve1(x,y,y*ts-t);
        if (x==y) ans = solve2(x,y*ts-t);
        if (x> y) ans = solve3(x,y,y*ts-t);
        // printf("del = %lld\n",ans);
        // printf("new all = %lld\n",all+a[x]-t);
        ans = (all+a[x]-t) - ans;
        write(ans); putchar('\n');
    }
    return 0;
}
//g++ submit.cpp -o submit -Wall -Wl,--stack=512000000 -std=c++11 -O2