#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int inf = 0x7ffffffffffffff;
ostream& operator<<(ostream& out, __int128 x) {
    if (x == 0) {
        out << "0";
        return out;
    }
    bool neg = (x < 0);
    x = (x < 0) ? -x : x;
    string str;
    while (x) str += (char)('0' + x % 10), x /= 10;
    reverse(str.begin(), str.end());
    if (neg) 
        str = '-' + str;
    out << str;
    return out;
}
int n, m, q, T;
int a[1000005], stk[1000005], sz;
struct Data_Structure {
    int r, n;
    __int128 ans;
    vector<signed> tor[20];
    vector<__int128> a, val[20];
    void ini(int x) {
        r = x, n = a.size();
        a.emplace_back(inf);
        for (__int128 i = 0, c = inf; i < n; i++) a[i] = i * T - a[i], c = min(c, a[i]), ans += c;
        for (int i = 0; i < 20; i++) val[i].resize(n + 1), tor[i].resize(n + 1);
        tor[0][n] = stk[sz = 0] = n;
        for (int i = n - 1; ~i; i--) {
            while (sz && a[stk[sz]] > a[i]) --sz;
            val[0][i] = a[i] * (stk[sz] - i), tor[0][i] = stk[sz];
            stk[++sz] = i;
        }
        for (int i = 1; i < 20; i++) {
            for (int j = 0; j <= n; j++) {
                tor[i][j] = tor[i - 1][tor[i - 1][j]];
                val[i][j] = val[i - 1][j] + val[i - 1][tor[i - 1][j]];
            }
        }
    }
    pair<__int128, __int128> f(int L, int R, __int128 x, int v = 0) {
        L = L / m + (L % m > r);
        R = R / m - (R % m < r);
        if (L > R) 
            return make_pair(x, (R - L + 1) * v * T);
        // cout << r << " " << L << " " << R << " " << x << "\n";
        int q = L, p = R + 1;
        if (a[L] <= x) 
            p = L;
        else {
            for (int i = 19; ~i; i--) {
                if (tor[i][q] > R) 
                    continue;
                if (a[tor[i][q]] <= x) 
                    p = tor[i][q];
                else 
                    q = tor[i][q];
            }
        }
        // cout << p << "\n";
        __int128 ret;
        ret = (p - L) * x;
        for (int i = 19; ~i; i--) {
            if (tor[i][p] <= R) 
                ret += val[i][p], p = tor[i][p];
        }
        // cout << p << " p\n";
        ret += (R - p + 1) * a[p];
        ret += (R - L + 1) * v * T;
        // cout << x << " " << a[p] << "\n";
        // cout << min(x, p <= r ? a[p] : inf) << " " << ret << "\n";
        return make_pair(min(x, p <= r ? a[p] : inf), ret);
    }
} ds[5];
__int128 bans;
int V[5];
void fv(__int128& s, __int128& p, __int128 v) { (p <= v) ? (s += p) : (p = v, s += v); }
signed main() {
    // freopen("dp.in", "r", stdin);
    // freopen("dp.out", "w", stdout);
    cin >> n >> m >> q >> T;
    for (int i = 0; i < n; i++) cin >> a[i], ds[i % m].a.emplace_back(a[i]), bans += (i / m) * T - a[i];
    for (int i = 0; i < m; i++) ds[i].ini(i);
    while (q--) {
        int x, v;
        __int128 tmp = bans, c;
        __int128 ans = 0;
        cin >> x >> v, --x;
        bans += a[x], bans -= v;
        int y = lower_bound(a, a + n, v) - a;
        y -= (y > x);
        // cout << x << " " << y << " x y\n";
        if (x == y) {
            for (int i = 0; i < m; i++) x % m != i ? (ans += ds[i].ans) : 0;
            pair<__int128, __int128> p = ds[x % m].f(0, x - 1, inf);
            c = p.first, ans += p.second;
            fv(ans, c, (x / m) * T - v);
            p = ds[x % m].f(x + 1, n - 1, c);
            ans += p.second;
        } else if (x < y) {
            for (int i = 0; i < m - 1; i++) {
                pair<__int128, __int128> p = ds[i].f(0, x - 1, inf); ans += p.second;
                p = ds[i + 1].f(x + 1, y, p.first); c = p.first; ans += p.second;
                if (y % m == i) 
                    fv(ans, c, (y / m) * T - v);
                p = ds[i].f(y + 1, n - 1, c); ans += p.second;
            }
            // cout << "----------------------------\n";
            pair<__int128, __int128> p = ds[m - 1].f(0, x - 1, inf); ans += p.second;
            p = ds[0].f(x + 1, y, p.first + T); c = p.first; ans += p.second;
            if (y % m == m - 1) 
                fv(ans, c, (y / m + 1) * T - v);
            p = ds[m - 1].f(y + 1, n - 1, c - T); ans += p.second;
            ans -= T * ((y + 1) / m - x / m);
        } else {
            for (int i = 1; i < m; i++) {
                pair<__int128, __int128> p = ds[i].f(0, y - 1, inf); c = p.first, ans += p.second;
                if (y % m == i) 
                    fv(ans, c, (y / m) * T - v);
                p = ds[i - 1].f(y, x - 1, c); ans += p.second;
                p = ds[i].f(x + 1, n - 1, p.first); ans += p.second;
            }
            pair<__int128, __int128> p = ds[0].f(0, y - 1, inf); c = p.first, ans += p.second;
            if (y % m == 0) 
                fv(ans, c, (y / m) * T - v);
            p = ds[m - 1].f(y, x - 1, c - T, 1); ans += p.second;
            p = ds[0].f(x + 1, n - 1, p.first + T); ans += p.second;
            // ans += T * ((x - 1) / m - (y / m - (y % m < m - 1)) + 1);
        }
        // cout << bans << " " << ans << "\n";
        cout << bans - ans << "\n";
        // cout << bans - ans << " asdfasdfasdf\n";
        bans = tmp;
    }
    return 0;
}
/*
10 3 1 11
1 1 2 4 6 9 9 11 14 25 
5 20
*/