#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
int stk[1000010],top;
struct Num{
	int n;
	vector<long long> a;
	vector<long long> f[20],g[20];
	void init()
	{
		n=a.size();
		for(int i=0;i<20;i++) f[i].resize(n);
		for(int i=0;i<20;i++) g[i].resize(n);
		top=0;
		for(int i=n-1;~i;i--)
		{
			while(top&&a[stk[top]]<a[i]) top--;
			if(top) f[0][i]=stk[top],g[0][i]=a[i]*(stk[top]-i);
			else f[0][i]=n;
			stk[++top]=i;
		}
		for(int i=1;i<20;i++) for(int j=0;j+(1<<i)-1<n;j++)
			if(f[i-1][j]!=n) f[i][j]=f[i-1][f[i-1][j]],g[i][j]=g[i-1][j]+g[i-1][f[i-1][j]];
			else f[i][j]=n;
	}
	//这一段前面的最大值为 X 的情况下，让其处理 [l,r] 段。X_ 返回新的最大值，sum 返回权值之和。
	inline void calc(long long X,int l,int r,long long &X_,long long &sum)
	{
		// printf("calc(%lld %d %d)\n",X,l,r);
		if(l>r) return X_=X,void();
		int cur=l;
		if(a[l]<X)
		{
			for(int i=19;~i;i--) if(f[i][cur]&&f[i][cur]<=r&&a[f[i][cur]]<X)
				cur=f[i][cur];
			if(f[0][cur]>r)	return X_=X,sum+=X*(r-l+1),void();
			cur=f[0][cur];
			sum+=X*(cur-l);
		}
		for(int i=19;~i;i--) if(f[i][cur]&&f[i][cur]<=r)
			sum+=g[i][cur],cur=f[i][cur];
		sum+=a[cur]*(r-cur+1);
		X_=a[cur];
	}
}s[5];

int n,m,q,T,x,x_,t_;
int t[1000010],tt[10],rr[10];long long a[1000010],a_;
long long ans,sum,tmp;
inline int clc(int x,int r){return x>=r?(x-r)/m:-1;}
int main()
{
	n=Qread(),m=Qread(),q=Qread(),T=Qread();
	for(int i=0;i<n;i++) t[i]=Qread();

	for(int i=0,p,r;i<n;i++)
	{
		r=i%m,p=i/m;a[i]=t[i]-1ll*p*T;
		s[r].a.push_back(a[i]);
		sum+=a[i];
	}
	for(int i=0;i<m;i++)
		s[i].init(),tt[rr[i]=(i+1)%m]=i;

	for(int zzz=1;zzz<=q;zzz++)
	{
		ans=0;
		x=Qread()-1,t_=Qread();
		x_=lower_bound(t,t+n,t_)-t;
		if(x_==x)
		{
			a_=t_-1ll*(x_/m)*T;
			for(int r=0;r<m;r++) if(x_%m!=r)
				s[r].calc(-inf,0,clc(n-1,r),tmp,ans);
			else
			{
				s[r].calc(-inf,0,clc(x-1,r),tmp,ans);
				if(tmp<a_) tmp=a_;ans+=tmp;
				s[r].calc(tmp,clc(x,r)+1,clc(n-1,r),tmp,ans);
			}
		}
		else if(x_<x)
		{
			a_=t_-1ll*(x_/m)*T;
			for(int r=0;r<m;r++)
			{
				s[r].calc(-inf,0,clc(x_-1,r),tmp,ans);
				if(x_%m==r){if(tmp<a_) tmp=a_;ans+=tmp;}

				if(r) s[tt[r]].calc(tmp,clc(x_-1,tt[r])+1,clc(x-1,tt[r]),tmp,ans);
				else
				{
					s[tt[r]].calc(tmp+T,clc(x_-1,tt[r])+1,clc(x-1,tt[r]),tmp,ans);
					tmp-=T;
				}
				s[r].calc(tmp,clc(x,r)+1,clc(n-1,r),tmp,ans);
			}
		}
		else
		{
			a_=t_-1ll*((x_-1)/m)*T;
			for(int r=0;r<m;r++)
			{
				s[r].calc(-inf,0,clc(x-1,r),tmp,ans);
				if(r!=m-1) s[rr[r]].calc(tmp,clc(x,rr[r])+1,clc(x_-1,rr[r]),tmp,ans);
				else
				{
					s[rr[r]].calc(tmp-T,clc(x,rr[r])+1,clc(x_-1,rr[r]),tmp,ans);
					tmp+=T;
				}
				if((x_-1)%m==r){if(tmp<a_) tmp=a_;ans+=tmp;}
				s[r].calc(tmp,clc(x_-1,r)+1,clc(n-1,r),tmp,ans);
			}
		}

		printf("%lld\n",ans-(sum-a[x]+a_));
	}
	return 0;
}