#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#define int long long
using namespace std;
const int MAXN=1e6+10;
const ll INF=1e18;
int n,m,q,t[MAXN],top,s[MAXN];
ll T;__int128 S,now,ans;
struct node
{
    int I,n;vector <int> t,f[20];
    vector <ll> w,h[20],g[20];
    inline ll Q(int l,int r)
    {
        int t=__lg(r-l+1);
        return max(h[t][r],h[t][l+(1<<t)-1]);
    }
    inline void calc(int l,int r,int del=0)
    {
        l=ceil((l-I)*1.0/m),r=floor((r-I)*1.0/m);
        if(l>r||!n) return ;del=-del*T;
        if(Q(l,r)+del<=now){ans+=(r-l+1)*now;return ;}
        int L=l,R=r;while(L<R)
            {int m=(L+R)>>1;(Q(l,m)+del>now)?R=m:L=m+1;}
        ans+=(L-l)*now;int tmp=L;
        for(int i=__lg(n);~i;--i)
            if(f[i][L]&&f[i][L]<=r) ans+=g[i][L],L=f[i][L];
        ans+=(L-tmp)*del;
        now=w[L]+del,ans+=(r-L+1)*now;return ;
    }
    inline void init()
    {
        n=t.size(),top=0,w.resize(n);
        for(int i=0;i<=__lg(n);++i)
            f[i].resize(n),g[i].resize(n),h[i].resize(n);
        for(int i=0;i<n;++i)
        {
            S+=(h[0][i]=w[i]=t[i]-i*T);
            for(int j=1;j<=__lg(i+1);++j)
                h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
        }
        for(int i=n-1;~i;--i)
        {
            while(top&&w[s[top]]<=w[i]) --top;
            g[0][i]=w[i]*((f[0][i]=s[top])-i),s[++top]=i;
            for(int j=1;f[j-1][i];++j)
                f[j][i]=f[j-1][f[j-1][i]],
                g[j][i]=g[j-1][i]+g[j-1][f[j-1][i]];
        }
    }
}o[5];
inline void calc(ll num)
    {if(num>now) now=num;ans+=now;}
inline void write(__int128 num)
{
    if(!num) return ;write(num/10);
    cout<<(int)(num%10);return ;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("shuju.txt","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m>>q>>T;
    for(int i=0;i<m;++i) o[i].I=i;
    for(int i=0;i<n;++i)
        cin>>t[i],o[i%m].t.push_back(t[i]);
    for(int i=0;i<m;++i) o[i].init();
    for(int x,y;q;--q)
    {
        cin>>x>>y;--x,ans=0;
        int k=upper_bound(t,t+n,y)-t;
        if(x==k)
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,x-1);
                if(x%m==i) calc(y-(x/m)*T);
                o[i].calc(x+1,n-1);
            }
        }
        else if(x<k)
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,x-1);
                o[(i+1)%m].calc(x+1,k-1,-(i==m-1));
                if((k-1)%m==i) calc(y-((k-1)/m)*T);
                o[i].calc(k,n-1);
            }
        }
        else
        {
            for(int i=0;i<m;++i)
            {
                now=-INF,o[i].calc(0,k-1);
                if(k%m==i) calc(y-(k/m)*T);
                o[(i+m-1)%m].calc(k,x-1,+(i==0));
                o[i].calc(x+1,n-1);
            }
        }
        write(ans-(S-t[x]+y)),cout<<'\n';
    }
    return 0;
}

answer.code:9:7: error: ‘ll’ does not name a type
    9 | const ll INF=1e18;
      |       ^~
answer.code:11:1: error: ‘ll’ does not name a type
   11 | ll T;__int128 S,now,ans;
      | ^~
answer.code:15:13: error: ‘ll’ was not declared in this scope
   15 |     vector <ll> w,h[20],g[20];
      |             ^~
answer.code:15:15: error: template argument 1 is invalid
   15 |     vector <ll> w,h[20],g[20];
      |               ^
answer.code:15:15: error: template argument 2 is invalid
answer.code:16:12: error: ‘ll’ does not name a type
   16 |     inline ll Q(int l,int r)
      |            ^~
answer.code: In member function ‘void node::calc(long long int, long long int, long long int)’:
answer.code:24:38: error: ‘T’ was not declared in this scope
   24 |         if(l>r||!n) return ;del=-del*T;
      |                                      ^
answer.code:25:12: error: ‘Q’ was not declared in this scope
   25 |         if(Q(l,r)+del<=now){ans+=(r-l+1)*now;return ;}
      |            ^
answer.code:27:30: error: ‘Q’ was not declared in this scope
   27 |             {int m=(L+R)>>1;(Q(l,m)+del>now)?R=m:L=m+1;}
      |                              ^
answer.code:30:46: error: invalid types ‘int[long long int]’ for array subscript
   30 |             if(f[i][L]&&f[i][L]<=r) ans+=g[i][L],L=f[i][L];
      |                                              ^
answer.code:32:14: error: invalid types ‘int[long long int]’ for array subscript
   32 |         now=w[L]+del,ans+=(r-L+1)*now;return ;
      |              ^
answer.code: In member function ‘void node::init()’:
answer.code:36:28: error: request for member ‘resize’ in ‘((node*)this)->node::w’, which is of non-class type ‘int’
   36 |         n=t.size(),top=0,w.resize(n);
      |                            ^~~~~~
answer.code:38:33: error: request for member ‘resize’ in ‘((node*)this)->node::g[i]’, which is of non-class type ‘int’
   38 |             f[i].resize(n),g[i].resize(n),h[i].resize(n);
      |                                 ^~~~~~
answer.code:38:48: error: request for member ‘resize’ in ‘((node*)this)->node::h[i]’, which is of non-class type ‘int’
   38 |             f[i].resize(n),g[i].resize(n),h[i].resize(n);
      |                                                ^~~~~~
answer.code:41:21: error: invalid types ‘int[long long int]’ for array subscript
   41 |             S+=(h[0][i]=w[i]=t[i]-i*T);
      |                     ^
answer.code:41:26: error: invalid types ‘int[long long int]’ for array subscript
   41 |             S+=(h[0][i]=w[i]=t[i]-i*T);
      |                          ^
answer.code:41:37: error: ‘T’ was not declared in this scope
   41 |             S+=(h[0][i]=w[i]=t[i]-i*T);
      |                                     ^
answer.code:43:21: error: invalid types ‘int[long long int]’ for array subscript
   43 |                 h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
      |                     ^
answer.code:43:35: error: invalid types ‘int[long long int]’ for array subscript
   43 |                 h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
      |                                   ^
answer.code:43:45: error: invalid types ‘int[long long int]’ for array subscript
   43 |                 h[j][i]=max(h[j-1][i],h[j-1][i-(1<<j-1)]);
      |                                             ^
answer.code:47:25: error: invalid types ‘int[long long int]’ for array subscript
   47 |             while(top&&w[s[top]]<=w[i]) --top;
      |                         ^
answer.code:47:36: error: invalid types ‘int[long long int]’ for array subscript
   47 |             while(top&&w[s[top]]<=w[i]) --top;
      |                                    ^
answer.code:48:17: error: invalid types ‘int[long long int]’ for array subscript
   48 |             g[0][i]=w[i]*((f[0][i]=s[top])-i),s[++top]=i;
      |                 ^
answer.code:48:22: error: invalid types ‘int[long long int]’ for array subscript
   48 |             g[0][i]=w[i]*((f[0][i]=s[top])-i),s[++top]=i;
      |                      ^
answer.code:51:21: error: invalid types ‘int[long long int]’ for array subscript
   51 |                 g[j][i]=g[j-1][i]+g[j-1][f[j-1][i]];
      |                     ^
answer.code:51:31: error: invalid types ‘int[long long int]’ for array subscript
   51 |                 g[j][i]=g[j-1][i]+g[j-1][f[j-1][i]];
      |                               ^
answer.code:51:41: error: invalid types ‘int[__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}]’ for array subscript
   51 |                 g[j][i]=g[j-1][i]+g[j-1][f[j-1][i]];
      |                                         ^
answer.code: At global scope:
answer.code:55:13: error: variable or field ‘calc’ declared void
   55 | inline void calc(ll num)
      |             ^~~~
answer.code:55:18: error: ‘ll’ was not declared in this scope
   55 | inline void calc(ll num)
      |                  ^~
answer.code: In function ‘int main()’:
answer.code:70:19: error: ‘T’ was n...