#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
signed jp[1000010][20];
__int128 sum[1000010][20];
__int128 pre[1000010];
int stk[5][1000010],top[5];
int a[1000010],b[1000010],n,m,q,t;
pair<pair<int,int>,__int128> calc(pair<int,int> add,pair<int,int> ori){//premax prenum (extra add)
	int maxv=ori.first,k=ori.second+1;
	__int128 ans=0;
	if(add.first==-1){
		int cg=add.second;
		if(cg-k*t<maxv) ans=maxv-(cg-k*t);
		else maxv=cg-k*t;
		return make_pair(make_pair(maxv,k),ans);
	}
	int l=add.first,r=add.second;
	//ori del=pos/m
	//rel del=(pos-l)/m+k
	int now=l;
	for(int i=19;i>=0;i--){
		if(jp[now][i]>r) continue;
		if(b[jp[now][i]]-(k-l/m)*t<=maxv) now=jp[now][i];
	}
	if(b[now]-(k-l/m)*t<=maxv&&jp[now][0]>r){
//		cout<<maxv*((r-l)/m+1)<<" "<<(int)pre[r]<<" "<<(int)pre[l-m]<<" "<<(k-l/m)*t*((r-l)/m+1)<<" ";
		ans+=(__int128)maxv*((r-l)/m+1)-((pre[r]-((l>m)?pre[l-m]:0))-(__int128)(k-l/m)*t*((r-l)/m+1));
		k+=(r-l)/m;
		return make_pair(make_pair(maxv,k),ans);
	}
	else{
		if(b[now]-(k-l/m)*t<=maxv) now=jp[now][0];
		ans+=(__int128)maxv*((now-l)/m)-((((now>m)?pre[now-m]:0)-((l>m)?pre[l-m]:0))-(__int128)(k-l/m)*t*((now-l)/m));
		maxv=b[now]-(k-l/m)*t;
		for(int i=19;i>=0;i--){
			if(jp[now][i]>r) continue;
			ans+=sum[now][i];
			now=jp[now][i];
			maxv=b[now]-(k-l/m)*t;
		}
//		cout<<maxv<<" "<<(k-l/m)<<" "<<b[now]<<" "<<now<<" ";
//		cout<<maxv*((r-now)/m+1)<<" "<<(int)((pre[r]-((now>m)?pre[now-m]:0)))<<" "<<(k-l/m)*t*((r-now)/m+1)<<" ";
		ans+=(__int128)maxv*((r-now)/m+1)-((pre[r]-((now>m)?pre[now-m]:0))-(__int128)(k-l/m)*t*((r-now)/m+1));
		k+=(r-l)/m;
		return make_pair(make_pair(maxv,k),ans);
	}
}
void print(__int128 val){
	if(val>=10) print(val/10);
	putchar((val%10)+'0');
}
signed main(){
	cin>>n>>m>>q>>t;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]-(i/m)*t;
	for(int i=1;i<=n+m;i++) pre[i]=(i<=m)?b[i]:(b[i]+pre[i-m]);
	for(int i=1;i<=m;i++) stk[(n+i)%m][0]=n+i,jp[n+i][0]=n+i;
	for(int i=n;i>=1;i--){
		int bel=i%m;
		while(top[bel]&&b[stk[bel][top[bel]]]<b[i]) top[bel]--;
		jp[i][0]=stk[bel][top[bel]]; sum[i][0]=(__int128)((jp[i][0]-i)/m)*b[i]-(pre[jp[i][0]-m]-((i>m)?pre[i-m]:0));
		stk[bel][++top[bel]]=i;
	}
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n+m;i++){
			jp[i][j]=jp[jp[i][j-1]][j-1];
			sum[i][j]=sum[i][j-1]+sum[jp[i][j-1]][j-1];
		}
	}
	while(q--){
		int x,cg; cin>>x>>cg;
		int pos=upper_bound(a+1,a+n+1,cg)-a-1;
		int tag1=x-1,tag2=pos;
		vector<pair<int,int>> vc[6];
		if(tag1==min(tag1,tag2)&&tag2==min(tag1,tag2)){
			int nows=1;
			for(int i=1;i<=m;i++){
				if(i<=tag1) vc[(nows+i-1)%m].push_back(make_pair(i,(tag1-i)/m*m+i));
			}
			(nows+=tag1)%=m;
			vc[nows].push_back(make_pair(-1,cg));
			(nows+=1)%=m;
			for(int i=1;i<=m;i++){
				if(tag1+i+1<=n) vc[(nows+i-1)%m].push_back(make_pair(tag1+i+1,(n-(tag1+i+1))/m*m+tag1+i+1));
			}
		}
		else if(tag2==min(tag1,tag2)){
			int nows=1;
			for(int i=1;i<=m;i++){
				if(i<=tag2) vc[(nows+i-1)%m].push_back(make_pair(i,(tag2-i)/m*m+i));
			}
			(nows+=tag2)%=m;
			vc[nows].push_back(make_pair(-1,cg));
			(nows+=1)%=m;
			for(int i=1;i<=m;i++){
				if((tag2+i)<=max(tag1,tag2)) vc[(nows+i-1)%m].push_back(make_pair(tag2+i,(max(tag1,tag2)-(tag2+i))/m*m+tag2+i));
			}
			(nows+=(tag1-tag2))%=m;
			for(int i=1;i<=m;i++){
				if(tag1+i+1<=n) vc[(nows+i-1)%m].push_back(make_pair(tag1+i+1,(n-(tag1+i+1))/m*m+tag1+i+1));
			}
		}
		else{
			int nows=1;
			for(int i=1;i<=m;i++){
				if(i<=tag1) vc[(nows+i-1)%m].push_back(make_pair(i,(tag1-i)/m*m+i));
			}
			(nows+=tag1)%=m;
			for(int i=1;i<=m;i++){
				if((tag1+i+1)<=tag2) vc[(nows+i-1)%m].push_back(make_pair(tag1+i+1,(tag2-(tag1+i+1))/m*m+tag1+i+1));
			}
			(nows+=tag2-tag1-1)%=m;
			vc[nows].push_back(make_pair(-1,cg));
			(nows+=1)%=m;
			for(int i=1;i<=m;i++){
				if(tag2+i<=n) vc[(nows+i-1)%m].push_back(make_pair(tag2+i,(n-(tag2+i))/m*m+tag2+i));
			}
		}
		__int128 ans=0;
		for(int i=0;i<m;i++){
			pair<int,int> tmp=make_pair(-1e18,0);
			for(auto v:vc[i]){
				auto nxt=calc(v,tmp);
				tmp=nxt.first;
				ans+=nxt.second;
//				cout<<v.first<<" "<<v.second<<" "<<tmp.first<<" "<<tmp.second<<" "<<(long long)ans<<"  ";
			}
//			cout<<(long long)ans<<"\n";
		}
		print(ans); putchar(10);
	}
	return 0;
}