#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(ll x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(ll x){write(x), putchar(32);}
	inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 1e6+5;
const int mod = 998244353;
const ll inf = 1e18;

int n, m, q, T, anc[20][MAXN], b[MAXN];
int len[MAXN], nxt[MAXN], topf, stk[MAXN], x, t;

vc<ll> num[10];

ll S, sum[20][MAXN], a[MAXN], ans, nowmaxn[10], maxr[10];

inline void prework(){
	for(int i=0;i<m;++i){
		topf=0; stk[0]=num[i].back()+m;
		for(int j=len[i];j>=1;--j){
			//(i,j) - > j*m+i
			while(topf && a[stk[topf]]<a[num[i][j]]) --topf;
			nxt[num[i][j]]=stk[topf]; stk[++topf]=num[i][j];
		}
	}
	for(int i=1;i<=n;++i)
		sum[0][i]=1ll*(nxt[i]-i)/m*a[i], anc[0][i]=nxt[i];
	for(int i=1;i<=19;++i)
		for(int j=1;j<=n;++j) sum[i][j]=sum[i-1][j]+sum[i-1][anc[i-1][j]], anc[i][j]=anc[i-1][anc[i-1][j]];
	return ;
}

inline pair<ll,ll> add(ll maxn, int g, int l, int r, ll delta){
	if(l>r) return mk(maxn,0ll);
	int p=num[g][l], pos=r, lmt=num[g][r];
	if(a[p]+delta>maxn) pos=p;
	else{
		int now=p;
		for(int i=19;i>=0;--i)
			if(anc[i][now] && a[anc[i][now]]+delta<=maxn) now=anc[i][now];
		now=anc[0][now];
		if(now==0 || now>lmt) pos=-1;
		else pos=now;
	}
	if(pos==-1) return mk(maxn,maxn*(r-l+1));
	ll co=maxn*(pos-p)/m; int now=pos;
	//cerr << "co=" << co << ' ' << now << ' ' << lmt << endl;
	for(int i=19;i>=0;--i)
		if(anc[i][now] && anc[i][now]<=lmt) co+=sum[i][now]+delta*((anc[i][now]-now)/m), now=anc[i][now];
	co+=(a[now]+delta)*((lmt-now)/m+1);
	return mk(a[now]+delta,co);
}	

inline int lower_bound(int x, int v){
	int l=1, r=len[x], mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(num[x][mid]>=v) r=mid-1;
		else l=mid+1;
	}
	return l;
}

inline int upper_bound(int x, int v){
	int l=1, r=len[x], mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(num[x][mid]>v) r=mid-1;
		else l=mid+1;
	}
	return l;
}

inline void show(){
	for(int i=0;i<m;++i) cout << "group:" << i << ' ' << nowmaxn[i] << ' ' << maxr[i] << endl;
	cout << "ans=" << ans << endl;	
}

inline void solve(){
	x=read(), t=read(); ans=0;
	int newrk=upper_bound(b+1,b+1+n,t)-b;
	// oldrk : x
	// newrk : newrk
	//cerr << "oldrk:" << x << ' ' << "newrk:" << newrk << endl;
	for(int i=0;i<m;++i) nowmaxn[i]=-inf, maxr[i]=0;
	int lmt=min(x,newrk), lmt2=max(x,newrk); pair<ll,ll> tmp;
	for(int i=0;i<m;++i){
		int u=lower_bound(i,lmt)-1; maxr[i]=u;
		//cerr << "u=" << u << endl;
		tmp=add(nowmaxn[i],i,1,u,0); ans+=tmp.se; nowmaxn[i]=tmp.fi;
	}
	//show();
	int which=newrk%m, l, r, delta;
	if(newrk<=x){
		if(nowmaxn[which]<1ll*t-1ll*maxr[which]*T-T) ans+=1ll*t-1ll*maxr[which]*T-T, nowmaxn[which]=1ll*t-1ll*maxr[which]*T-T;
		else ans+=nowmaxn[which]; maxr[which]++;
		l=newrk, r=x-1, delta=-1;
		for(int i=0;i<m;++i){
			int u=(i+delta+m)%m;
			int L=lower_bound(u,l);
			int R=upper_bound(u,r)-1;
			tmp=add(nowmaxn[i],u,L,R,1ll*(L-maxr[i]-1)*T); ans+=tmp.se; nowmaxn[i]=tmp.fi; maxr[i]+=R-L+1;
		}
	}
	else{
		delta=1; 
		l=x+1, r=newrk, delta=1;
		for(int i=0;i<m;++i){
			int u=(i+delta+m)%m;
			int L=lower_bound(u,l);
			int R=upper_bound(u,r)-1;
			//cerr << "range:" << i << ' ' << u << ' ' << L << ' ' << R << ' ' << "l=" << l << endl;
			tmp=add(nowmaxn[i],u,L,R,1ll*(L-maxr[i]-1)*T); ans+=tmp.se; nowmaxn[i]=tmp.fi; maxr[i]+=R-L+1;
		}
		if(nowmaxn[which]<1ll*t-1ll*maxr[which]*T-T) ans+=1ll*t-1ll*maxr[which]*T-T, nowmaxn[which]=1ll*t-1ll*maxr[which]*T-T;
		else ans+=nowmaxn[which]; maxr[which]++;
	}
	//show();
	for(int i=0;i<m;++i){
		int u=upper_bound(i,lmt2);
		//cerr << "range:" << u << ' ' << len[i] << ' ' << which << endl;
		tmp=add(nowmaxn[i],i,u,len[i],0); ans+=tmp.se; nowmaxn[i]=tmp.fi; maxr[i]=len[i];	
	}
	//show();
	//cerr << "ans=" << ans << endl;
	//cerr << "S=" << S << endl;
	eprint(ans-(S-b[x]+t));
}

signed main(){
	n=read(), m=read(), q=read(), T=read();
	for(int i=0;i<m;++i) num[i].pb(0);
	for(int i=1;i<=n;++i) a[i]=read(), num[i%m].pb(i), S+=a[i], b[i]=a[i];
	for(int i=0;i<m;++i) len[i]=int(num[i].size())-1;
	for(int i=0;i<m;++i)
		for(int j=1;j<=len[i];++j) a[num[i][j]]-=1ll*j*T, S-=1ll*j*T;
	prework(); while(q--) solve();
	return 0;
}