//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int n,m,q;
ll T;
ll a[1001000];
ll psum[1001000][5];
ll b[1001000];
ll sum[5];
ll rsum[1001000][5];
ll psum1[1001000][5];
ll pmx[1001000][5];
ll nxt[20][1001000][5];
vector<pii> vq[1001000];
ll Answer[1001000];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q>>T;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i]+T*n-T*(i/m);
	}
	for(int i=1;i<=n+666;i++)
		for(int j=0;j<m;j++)
			psum[i][j]=psum[i-1][j]+(i%m==j?b[i]:0);
	vector<pair<ll,int>> vec[5];
	for(int i=n;i>=1;i--)
	{
		ll val=b[i];
		int p=i%m;
		int tot=1;
		while(sz(vec[p])&&vec[p].back().first<=val)
		{
			sum[p]-=vec[p].back().first*vec[p].back().second;
			tot+=vec[p].back().second;
			vec[p].pop_back();
		}
		vec[p].pb(val,tot);
		sum[p]+=val*tot;
		for(int j=0;j<m;j++)
			rsum[i][j]=sum[j];
	}
	ll mx[5];
	memset(mx,0,sizeof(mx));
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<5;j++)
			psum1[i][j]=psum1[i-1][j]+(i%m==j?max(0ll,mx[j]-b[i]):0);
		mx[i%m]=max(mx[i%m],b[i]);
		for(int j=0;j<5;j++)
			pmx[i][j]=mx[j];
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<m;j++)
			nxt[0][i][j]=(i%m==j?b[i]:0);
	for(int j=0;j<m;j++)
		for(int x=1;x<20;x++)
			for(int i=1;i<=n;i++)
				if(i+(1<<(x-1))>n)
					nxt[x][i][j]=nxt[x-1][i][j];
				else
					nxt[x][i][j]=max(nxt[x-1][i][j],nxt[x-1][i+(1<<x-1)][j]);
	for(int ind=1;ind<=q;ind++)
	{
		int p;
		ll v;
		cin>>p>>v;
		int p2=lower_bound(a+1,a+n+1,v)-a;
		if(p==p2||p+1==p2)
		{
			p2--;
			ll ans=0;
			for(int i=0;i<m;i++)
				if(i!=p%m)
					ans+=psum1[n][i];
				else
				{
					ans+=psum1[p-1][i];
					ll v2=v+T*n-T*(p/m);
					ans+=max(0ll,pmx[p-1][i]-v2);
					ll cmx=max(pmx[p-1][i],v2);
					int cur=p+1;
					for(int j=19;j>=0&&cur<=n;j--)
						if(nxt[j][cur][i]<=cmx)
							cur+=(1<<j);
					cur--;
					cur=min(cur,n);
					while(cur%m!=i&&cur>=0) cur--;
					if(cur>p)
						ans+=cmx*(cur-p)/m+rsum[cur+1][i];
					else
						ans+=rsum[p+1][i];
					ans-=psum[n][i]-psum[p][i];
				}
			Answer[ind]=ans;
		}
		else if(p<p2)
		{
			p2--;
			ll ans=0;
			ll nb=v+T*n-T*(p2/m);
			for(int i=0;i<m;i++)
			{
				ans+=psum1[p-1][i];
				int i2=(i+1)%m;
				ll cmx=pmx[p-1][i];
				if(!i2) cmx-=T;
				int cur=p+1;
				for(int j=19;j>=0&&cur<=p2;j--)
					if(nxt[j][cur][i2]<=cmx)
						cur+=(1<<j);
				cur--;
				cur=min(cur,p2);
				while(cur%m!=i2&&cur>=0) cur--;
				int nxt=p+1;
				while(nxt%m!=i2) nxt++;
				if(cur>=nxt)
				{
					ans+=cmx*(cur-nxt+m)/m;
					vq[cur+m].pb(p2,ind);
				}
				else
					vq[nxt].pb(p2,ind);
				ans-=psum[p2][i2]-psum[p][i2];
				int x=p+1,len=p2-p;
				for(int j=0;j<20;j++) if(len>>j&1)
				{
					cmx=max(cmx,::nxt[j][x][i2]);
					x+=(1<<j);
				}
				if(!i2) cmx+=T;
				if(p2%m==i)
				{
					ans+=max(0ll,cmx-nb);
					cmx=max(cmx,nb);
				}
				cur=p2+1;
				for(int j=19;j>=0&&cur<=n;j--)
					if(::nxt[j][cur][i]<=cmx)
						cur+=(1<<j);
				cur--;
				cur=min(cur,n);
				nxt=p2+1;
				while(nxt%m!=i) nxt++;
				while(cur%m!=i&&cur>=0) cur--;
				if(cur>=nxt)
					ans+=cmx*(cur-nxt+m)/m+rsum[cur+1][i];
				else
					ans+=rsum[nxt][i];
				ans-=psum[n][i]-psum[nxt-1][i];
			}
			Answer[ind]=ans;
		}
		else
		{
			ll ans=0;
			ll nb=v+T*n-T*(p2/m);
			for(int i=0;i<m;i++)
			{
				ans+=psum1[p2-1][i];
				int i2=(i+m-1)%m;
				ll cmx=pmx[p2-1][i];
				int cur=p2;
				if(p2%m==i)
				{
					ans+=max(0ll,cmx-nb);
					cmx=max(cmx,nb);
				}
				if(!i) cmx+=T;
				for(int j=19;j>=0&&cur<p;j--)
					if(nxt[j][cur][i2]<=cmx)
						cur+=(1<<j);
				cur--;
				cur=min(cur,p-1);
				while(cur%m!=i2&&cur>=0) cur--;
				int nxt=p2;
				while(nxt%m!=i2) nxt++;
				if(cur>=nxt)
				{
					ans+=cmx*(cur-nxt+m)/m;
					vq[cur+m].pb(p-1,ind);
				}
				else
					vq[nxt].pb(p-1,ind);
				ans-=psum[p-1][i2]-psum[p2-1][i2];
				int x=p2,len=p-p2;
				for(int j=0;j<20;j++) if(len>>j&1)
				{
					cmx=max(cmx,::nxt[j][x][i2]);
					x+=(1<<j);
				}
				if(!i) cmx-=T;
				cur=p+1;
				for(int j=19;j>=0&&cur<=n;j--)
					if(::nxt[j][cur][i]<=cmx)
						cur+=(1<<j);
				cur--;
				cur=min(cur,n);
				nxt=p+1;
				while(nxt%m!=i) nxt++;
				while(cur%m!=i) cur--;
				if(cur>=nxt)
					ans+=cmx*(cur-nxt+m)/m+rsum[cur+1][i];
				else
					ans+=rsum[nxt][i];
				ans-=psum[n][i]-psum[nxt-1][i];
			}
			Answer[ind]=ans;
		}
	}
	for(int i=0;i<5;i++)
		vec[i].clear();
	vector<int> vc[5];
	vector<ll> vs[5];
	for(int i=0;i<5;i++)
	{
		vc[i].pb(0);
		vs[i].pb(0);
	}
	for(int i=n;i>=1;i--)
	{
		ll val=b[i];
		int p=i%m;
		int tot=1;
		while(sz(vec[p])&&vec[p].back().first<=val)
		{
			sum[p]-=vec[p].back().first*vec[p].back().second;
			tot+=vec[p].back().second;
			vec[p].pop_back();
			vs[p].pop_back();
			vc[p].pop_back();
		}
		vec[p].pb(val,tot);
		vc[p].pb(vc[p].back()+tot);
		vs[p].pb(vs[p].back()+val*tot);
		sum[p]+=val*tot;
		for(int j=0;j<m;j++)
			rsum[i][j]=sum[j];
		for(auto pr:vq[i])
		{
			if(pr.first<i) continue;
			int cnt=(pr.first-i)/m+1;
			int p=i%m;
			int L=0,R=sz(vec[p]);
			while(L<R)
			{
				int mid=(L+R)/2;
				if(vc[p].back()-vc[p][mid]<=cnt)
					R=mid;
				else
					L=mid+1;
			}
			Answer[pr.second]+=vs[p].back()-vs[p][L];
			cnt-=vc[p].back()-vc[p][L];
			if(L)
				Answer[pr.second]+=vec[p][L-1].first*cnt;
		}
	}
	for(int i=1;i<=q;i++)
		cout<<Answer[i]<<'\n';
	return 0;
}