#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int n, m, q, T, Z, a[1000050];
struct S
{
    int n, l, f[1050][23], g[1050][23], p[1000050], b[1000050], s[1000050];
    void I()
    {
        for (int i = 0; i <= n + 1; ++i)
            for (int j = 0; j <= 21; ++j)
                f[i][j] = n + 1;
        for (int i = 0; i <= n; ++i)
        {
            b[i] = i * T - a[p[i]], Z += b[i];
            while (l && b[i] < b[s[l]])
                f[s[l]][0] = i, g[s[l]][0] = b[s[l]] * (i - s[l]), --l;
            s[++l] = i;
        }
        b[n + 1] = -1e18;
        for (int j = 1; 1 << j <= n; ++j)
            for (int i = 0; i <= n; ++i)
                f[i][j] = f[f[i][j - 1]][j - 1], g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
    }
    int L(int l) { return lower_bound(p + 1, p + n + 1, l) - p; }
    int R(int r) { return upper_bound(p + 1, p + n + 1, r) - p - 1; }
    void F(int l, int r, int d, int &u, int &o, int &c, int &z)
    {
        l = L(l), r = R(r), c += r - l + 1;
        int v = l;
        if (b[v] - d * T >= o)
        {
            for (int j = __lg(n); j >= 0; --j)
                if (b[f[v][j]] - d * T >= o)
                    v = f[v][j];
            v = f[v][0];
        }
        if (v <= r)
        {
            z += o * (v - d - u), u = v;
            for (int j = __lg(n); j >= 0; --j)
                if (f[u][j] <= r)
                    z += g[u][j] - d * T * (f[u][j] - u), u = f[u][j];
            o = b[u] - d * T, u -= d;
        }
    }
} P[6];
signed main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &q, &T), a[0] = -1e15;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i);
    for (int i = 1; i <= m; ++i)
    {
        for (int j = i; j <= n; j += m)
            P[i].p[++P[i].n] = j;
        P[i].I();
    }
    for (int i = 0, x, w; i < q; ++i)
    {
        scanf("%lld%lld", &x, &w);
        int y = upper_bound(a + 1, a + n + 1, w) - a - 1, _ = w;
        if (x <= y)
        {
            int s = 0;
            for (int j = 1; j <= m; ++j)
            {
                int u = 0, o = P[j].b[0], c = 0, z = 0;
                P[j].F(1, x - 1, 0, u, o, c, z);
                P[j % m + 1].F(x + 1, y, P[j % m + 1].L(x + 1) - c - 1, u, o, c, z);
                if ((x - 1) % m + 1 == j)
                {
                    ++c;
                    if (c * T - w < o)
                        z += o * (c - u), u = c, o = c * T - w;
                }
                P[j].F(y + 1, n, P[j].L(y + 1) - c - 1, u, o, c, z);
                z += o * (P[j].n - u + 1);
                s += z;
            }
            printf("%lld\n", Z + a[x] - _ - s);
        }
        else
        {
            int s = 0;
            for (int j = 1; j <= m; ++j)
            {
                int u = 0, o = P[j].b[0], c = 0, z = 0;
                P[j].F(1, y, 0, u, o, c, z);
                if ((x - 1) % m + 1 == j)
                {
                    ++c;
                    if (c * T - w < o)
                        z += o * (c - u), u = c, o = c * T - w;
                }
                P[j % m + 1].F(y + 1, x - 1, P[j % m + 1].L(y + 1) - c - 1, u, o, c, z);
                P[j].F(x + 1, n, P[j].L(x + 1) - c - 1, u, o, c, z);
                z += o * (P[j].n - u + 1);
                s += z;
            }
            printf("%lld\n", Z + a[x] - _ - s);
        }
    }
    return 0;
}