#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=(1<<28)+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,q,T,X[N],Y[N],pt[N],A[N];
ll ans[N];
ll mx[N];
struct DS{
	ll ms[N],sum[N],qsum[N];
	ll st[20][N];int siz[20][N];
	int k;
	void build(int kk){
		k=kk;
		ms[0]=-1e18;
		for(int i=1;i<=n;i++){
			ms[i]=ms[i-1],sum[i]=sum[i-1];
			if(i%m==k){
				if(ms[i]<A[i]) ms[i]=A[i]+T;
				else sum[i]+=ms[i]-A[i],ms[i]+=T;
			}
		}
		for(int i=1;i<=n;i++){
			qsum[i]=qsum[i-1];
			if(i%m==k) st[0][i]=A[i],siz[0][i]=1,qsum[i]+=A[i];
			else st[0][i]=-1e18,siz[0][i]=0;
		}
		for(int i=1;(1<<i)<=n;i++){
			for(int j=1;j+(1<<i)-1<=n;j++){
				st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]-1ll*T*siz[i-1][j]);
				siz[i][j]=siz[i-1][j]+siz[i-1][j+(1<<i-1)];
			}
		}
	}
	void jump(int i,int &q,int r){
		for(int j=19;~j;j--){
			if(q+(1<<j)-1<=r&&st[j][q]<=mx[i]){
				ans[i]+=(mx[i]+1ll*(siz[j][q]-1)*T+mx[i])*siz[j][q]/2-(qsum[q+(1<<j)-1]-qsum[q-1]);
				mx[i]+=1ll*siz[j][q]*T;
				q+=(1<<j);
			}
		}
	}
	vector<pii> Q[N];
	ll w[N],ssum[N];
	int s[N],sh;
	void calc(){
		for(int i=1;i<=n;i++) if(i%m==k) w[i]=A[i]-1ll*i/m*T;
		s[sh=0]=n+m;while(s[sh]%m!=k) s[sh]--;
		for(int i=n;i;i--){
			if(i%m==k){
				while(sh&&w[s[sh]]<w[i]) sh--;
				s[++sh]=i;
				int siz=(s[sh-1]-i)/m;
				ssum[sh]=ssum[sh-1]+(A[i]+A[i]+1ll*(siz-1)*T)*siz/2-(qsum[min(s[sh-1]-1,n)]-qsum[i-1]);
			}
			for(auto [y,id]:Q[i]){
				int l=0,r=sh,mid;
				while(l+1<r) mid=l+r>>1,(s[mid]<=y?r:l)=mid;
				int siz=(y-s[r])/m+1;
				mx[id]=A[s[r]]+1ll*siz*T;
				ans[id]+=ssum[sh]-ssum[r]+(A[s[r]]+A[s[r]]+1ll*(siz-1)*T)*siz/2-(qsum[y]-qsum[s[r]-1]);
				/*ll mx=-1e18;
				for(int j=i;j<=y;j++) if(j%m==k){
					if(A[j]>mx) mx=A[j]+T;
					else ans[id]+=mx-A[j],mx+=T;
				}
				::mx[id]=mx;
				gdb(id,mx);*/
			}
			Q[i].clear();
		}
	}

}f[5];
void Solve(){
	scanf("%d%d%d%d",&n,&m,&q,&T);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	for(int i=1;i<=q;i++) scanf("%d%d",&X[i],&Y[i]);
	for(int i=0;i<m;i++) f[i].build(i);
	for(int k=0;k<m;k++){
		for(int i=1;i<=q;i++){
			auto merge=[&](int x){
				if(mx[i]<x) mx[i]=x+T;
				else ans[i]+=mx[i]-x,mx[i]+=T;
			};
			if(Y[i]>=A[X[i]]){
				pt[i]=UB(A+1,A+n+1,Y[i])-A-1;
				ans[i]+=f[k].sum[X[i]-1];
				mx[i]=f[k].ms[X[i]-1]; 
				int q=X[i]+1;
				f[(k+1)%m].jump(i,q,pt[i]);
				if(q<=pt[i]) f[(k+1)%m].Q[q].emplace_back(pt[i],i),gdb(q,pt[i]);
				// for(int j=q;j<=pt[i];j++) if((j-1)%m==k) merge(A[j]);
				// gdb(i,mx[i]);
			}else{
				pt[i]=LB(A+1,A+n+1,Y[i])-A;
				mx[i]=f[k].ms[pt[i]-1];ans[i]+=f[k].sum[pt[i]-1];
				if(pt[i]%m==k) merge(Y[i]);
				int q=pt[i];
				f[(k-1+m)%m].jump(i,q,X[i]-1);
				if(q<X[i]) f[(k-1+m)%m].Q[q].emplace_back(X[i]-1,i);
				// for(int j=q;j<=pt[i];j++) if((j-1)%m==k) merge(A[j]);
			}
		}
		f[(k+1)%m].calc();f[(k-1+m)%m].calc();
		for(int i=1;i<=q;i++){
			auto merge=[&](int x){
				if(mx[i]<x) mx[i]=x+T;
				else ans[i]+=mx[i]-x,mx[i]+=T;
			};
			if(Y[i]>=A[X[i]]){
				if(pt[i]%m==k) merge(Y[i]);
				int q=pt[i]+1;
				f[k].jump(i,q,n);
				if(q<=n) f[k].Q[q].emplace_back(n,i);
				// for(int j=q;j<=n;j++) if(j%m==k) merge(A[j]);
			}else{
				int q=X[i]+1;
				f[k].jump(i,q,n);
				if(q<=n) f[k].Q[q].emplace_back(n,i);
				// for(int j=q;j<=n;j++) if(j%m==k) merge(A[j]);
			}
		}
		f[k].calc();
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}