#include <bits/stdc++.h>
#define int long long
#define i128 __int128
#define u (i128)1
#define inf 1e18
using namespace std;

template<typename T> void read(T &x) {
	T s = 0, w = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') w = 0; c = getchar(); }
	while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
	x = w ? s : -s;
}
template<typename T> void write(T x) {
	if (x < 0) {putchar('-'); x = ~(x - 1); }
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 1000010;
int n, m, q, T, t[N];
i128 addans;
int id(int x) {return x / m + (x % m != 0); }
int fdl(int p, int r) {while (p && p % m != r) --p; return p ? id(p) : -inf; }
int fdr(int p, int r) {while (p <= n && p % m != r) ++p; return p <= n ? id(p) : inf; }

struct node{
	int v; i128 sum;
	node operator + (const node &y) const {
		return (node) {y.v, sum + y.sum};
	}
	node operator + (const int &y) const {
		return (node) {min(v, y), sum + min(v, y)};
	}
};
struct bsk{
	int n, a[N], lg[N];
	vector<int> f[20];
	vector<i128> g[20];
	int stac[N], top;
	void init() {
		for (int i=0; i<=19; ++i)
			f[i].resize(n + 10), g[i].resize(n + 10);
		lg[1] = 0;
		for (int i=2; i<=n; ++i) lg[i] = lg[i >> 1] + 1;
		top = 0;
		for (int i=1; i<=n; ++i) {
			while (top && a[i] < a[stac[top]])
				f[0][stac[top]] = i, --top;
			stac[++top] = i;
		}
		while (top) f[0][stac[top--]] = n + 1;
		f[0][n + 1] = n + 1;
		for (int i=1; i<=n+1; ++i)
			g[0][i] = u * a[i] * (f[0][i] - i);
		for (int j=1; j<=19; ++j)
			for (int i=1; i<=n+1; ++i) {
				f[j][i] = f[j - 1][f[j - 1][i]];
				g[j][i] = g[j - 1][i] + g[j - 1][f[j - 1][i]];
			}
	}
	int nxtmin(int p, int v) {
		if (a[p] < v) return p;
		for (int i=19; i>=0; --i)
			if (f[i][p] <= n && a[f[i][p]] >= v) p = f[i][p];
		return f[0][p];
	}
	node query(int x, int d, int l, int r) {
		if (l > r) return (node) {x, 0};
		x -= d;
		int p = min(nxtmin(l, x), r + 1);
		i128 ret = u * d * (r - l + 1) + u * x * (p - l);
		for (int i=19; i>=0; --i)
			if (f[i][p] <= r) ret += g[i][p], p = f[i][p];
		ret += u * a[p] * (r - p + 1);
		return (node) {(p <= r ? a[p] : x) + d, ret};
	}
}h[5];

i128 solve0(int x, int y, int w) {
	i128 ret = 0;
	for (int j=0; j<m; ++j) {
		node tmp = h[j].query(inf, 0, 1, fdl(x - 1, j));
		int k = (j + 1) % m;
		tmp = tmp + h[k].query(tmp.v, T * (fdr(x, j) - fdr(x + 1, k)), fdr(x + 1, k), fdl(y, k));
		if (y % m == j) tmp = tmp + (T * id(y) - w);
		tmp = tmp + h[j].query(tmp.v, 0, fdr(y + 1, j), fdl(n, j));
		ret -= tmp.sum;
	}
	return ret;
}
i128 solve1(int x, int y, int w) {
	i128 ret = 0;
	for (int j=0; j<m; ++j) {
		node tmp = h[j].query(inf, 0, 1, fdl(x - 1, j));
		if (x % m == j) tmp = tmp + (T * id(x) - w);
		int k = (j - 1 + m) % m;
		tmp = tmp + h[k].query(tmp.v, T * (fdr(x + 1, j) - fdr(x, k)), fdr(x, k), fdl(y - 1, k));
		tmp = tmp + h[j].query(tmp.v, 0, fdr(y + 1, j), fdl(n, j));
		ret -= tmp.sum;
	}
	return ret;
}

signed main() {
	read(n), read(m), read(q), read(T);
	for (int i=1; i<=n; ++i) read(t[i]);
	for (int j=0; j<m; ++j) {
		int tot = 0;
		for (int i=j?j:m; i<=n; i+=m) {
			++tot;
			h[j].a[tot] = T * tot - t[i];
			addans += T * tot - t[i];
		}
		h[j].n = tot;
		h[j].init();
	}
	while (q--) {
		int x, v; read(x), read(v);
		int y = lower_bound(t + 1, t + n + 1, v) - t;
		int ret = addans + t[x] - v;
		if (v <= t[x]) ret += solve1(y, x, v);
		else ret += solve0(x, y - 1, v);
		write(ret), putchar(10);
	}
	return 0;
}