#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct op {
    vector<long long> p;

    void append(long long x) {
        p.push_back(x);
    }

    void Init() {

    }

    long long query(int l, int r, long long &x, int D) {
        if (l > r) return 0;
        pair<long long, long long> res = {0, x};
        for (int i = l; i <= r; ++i) {
            res.second = min(res.second, p[i] + D);
            res.first += res.second;
        }
        x = res.second;
        return res.first;
    }
} o[5];

long long query(int p, int q, int L, int R, long long &x, int D) {
    int l = (L - q) / p * p - 1, r = (R - q) / p * p + 1;
    while (l * p + q < L) ++l;
    while (r * p + q > R) --r;
    return o[q].query(l, r, x, D);
}

int a[N];

signed main() {
    int n, m, q, T; scanf("%d%d%d%d", &n, &m, &q, &T);
    long long S = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        o[i % m].append(1ll * (i / m) * T - a[i]);
        S += 1ll * (i / m) * T - a[i];
    }
    for (int i = 0; i < m; ++i) {
        o[i].Init();
    }
    while (q--) {
        int x, y; scanf("%d%d", &x, &y), --x;
        long long res = S + a[x] - y;
        int t = lower_bound(a, a + n, y) - a;
        if (t <= x) {
            for (int i = 0; i < m; ++i) {
                long long now = 1e18;
                res -= query(m, i, 0, t - 1, now, 0);
                if (t % m == i) {
                    now = min(now, 1ll * (t / m) * T - y);
                    res -= now;
                }
                res -= query(m, (i - 1 + m) % m, t, x - 1, now, (i % m == 0 ? T : 0));
                res -= query(m, i, x + 1, n - 1, now, 0);
            }
        } else {
            for (int i = 0; i < m; ++i) {
                long long now = 1e18;
                res -= query(m, i, 0, x - 1, now, 0);
                res -= query(m, (i + 1) % m, x + 1, t - 1, now, (i % m == m - 1 ? -T : 0));
                if ((t - 1) % m == i) {
                    now = min(now, 1ll * ((t - 1) / m) * T - y);
                    res -= now;
                }
                res -= query(m, i, t, n - 1, now, 0);
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}