#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int n, m, q, l, T, Z, a[1000050], b[1000050], s[1000050], f[1000050][23], g[1000050][23];
void F(int l, int r, int d, int &u, int &o, int &z)
{
    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;
    }
}
signed main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &q, &T);
    for (int i = 1; i <= n + 1; ++i)
        for (int j = 0; j <= 21; ++j)
            f[i][j] = n + 1;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", a + i), b[i] = i * T - a[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 = 1; 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];
    for (int i = 0, x, w; i < q; ++i)
    {
        scanf("%lld%lld", &x, &w);
        int y = lower_bound(a + 1, a + n + 1, w) - a, _ = w;
        if (y > x)
        {
            w = (y - 1) * T - w;
            int u, o, z = 0;
            if (x != 1)
                u = 1, o = b[1], F(1, x - 1, 0, u, o, z);
            else if (y != 2)
                u = 1, o = b[2] - T;
            else
                u = 1, o = w;
            F(x + 1, y - 1, 1, u, o, z);
            if (w < o)
                z += o * (y - 1 - u), u = y - 1, o = w;
            F(y, n, 0, u, o, z);
            z += o * (n - u + 1);
            printf("%lld\n", Z + a[x] - _ - z);
        }
        else
        {
            w = y * T - w;
            int u, o, z = 0;
            if (y != 1)
            {
                u = 1, o = b[1];
                for (int j = __lg(n); j >= 0; --j)
                    if (f[u][j] < y)
                        z += g[u][j], u = f[u][j];
                o = b[u];
            }
            else
                u = 1, o = w;
            if (w < o)
                z += o * (y - u), u = y, o = w;
            F(y, x - 1, -1, u, o, z);
            F(x + 1, n, 0, u, o, z);
            z += o * (n - u + 1);
            printf("%lld\n", Z + a[x] - _ - z);
        }
    }
    return 0;
}