#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 = 0) {
        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];

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 -= o[i].query(0, (t - i) / m, now);
                if (t % m == i) {
                    now = min(now, 1ll * (t / m) * T - y);
                    res -= now;
                }
                for (int j = t; j < x; ++j) {
                    if ((j + 1) % m == i) res -= o[j % m].query(j / m, j / m, now, (j % m == m - 1 ? T : 0));
                }
                for (int j = x + 1; j < n; ++j) {
                    if (j % m == i) res -= o[i].query(j / m, j / m, now);
                }
            }
        } else {
            for (int i = 0; i < m; ++i) {
                long long now = 1e18;
                for (int j = i; j < x; j += m) {
                    res -= o[i].query(j / m, j / m, now);
                }
                for (int j = x + 1; j < t; ++j) {
                    if ((j - 1) % m == i) res -= o[j % m].query(j / m, j / m, now, (j % m == 0 ? -T : 0));
                }
                if ((t - 1) % m == i) {
                    now = min(now, 1ll * ((t - 1) / m) * T - y);
                    res -= now;
                }
                for (int j = t; j < n; ++j) {
                    if (j % m == i) res -= o[i].query(j / m, j / m, now);
                }
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}