#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[1000050][23], g[1000050][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 ((y - 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 (y % m + 1 == j)
                {
                    ++c;
                    if (c * T - w < o)
                        z += o * (c - u), u = c, o = c * T - w;
                }
                P[(j + m - 2) % m + 1].F(y + 1, x - 1, P[(j + m - 2) % 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;
}

answer.code: In function ‘int main()’:
answer.code:51:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |     scanf("%lld%lld%lld%lld", &n, &m, &q, &T), a[0] = -1e15;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:53:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         scanf("%lld", a + i);
      |         ~~~~~^~~~~~~~~~~~~~~
answer.code:62:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |         scanf("%lld%lld", &x, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
/tmp/ccsXjR8N.o: in function `S::F(long long, long long, long long, long long&, long long&, long long&, long long&)':
answer.code:(.text._ZN1S1FExxxRxS0_S0_S0_[_ZN1S1FExxxRxS0_S0_S0_]+0x9f): relocation truncated to fit: R_X86_64_PC32 against symbol `T' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text._ZN1S1FExxxRxS0_S0_S0_[_ZN1S1FExxxRxS0_S0_S0_]+0x148): relocation truncated to fit: R_X86_64_PC32 against symbol `T' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text._ZN1S1FExxxRxS0_S0_S0_[_ZN1S1FExxxRxS0_S0_S0_]+0x185): relocation truncated to fit: R_X86_64_PC32 against symbol `T' defined in .bss section in /tmp/ccsXjR8N.o
/tmp/ccsXjR8N.o: in function `main':
answer.code:(.text.startup+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `T' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x10): relocation truncated to fit: R_X86_64_PC32 against symbol `q' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x19): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x20): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x5d): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x64): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x70): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccsXjR8N.o
answer.code:(.text.startup+0x94): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status