#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fir first
#define sec second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
const int MAXN=1e5+10; const long MOD=998244353;
int curver;
struct Vec{ unsigned a[3]; };
struct Mat{ unsigned a[3][3]; };
Vec operator+(Vec x,Vec y){ return {x.a[0]+y.a[0],x.a[1]+y.a[1],x.a[2]+y.a[2]}; }
Vec operator*(Vec x,const Mat& y){
    Vec z{};
    RNG(k,0,2){
        RNG(j,0,2) z.a[j]+=x.a[k]*y.a[k][j];
    }
    return z;
}
Mat operator*(const Mat& x,const Mat& y){
    Mat z{};
    RNG(k,0,2){
        RNG(i,0,2){
            RNG(j,0,2) z.a[i][j]+=x.a[i][k]*y.a[k][j];
        }
    }
    return z;
}
constexpr Mat I{{{1,0,0},{0,1,0},{0,0,1}}};
struct SGT{
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)/2)
    struct{ Vec x; Mat tag; } T[MAXN*4];
    void pushup(int u){ T[u].x=T[ls].x+T[rs].x; }
    void build(int u,int l,int r){
        T[u].tag=I;
        if(l==r){ T[u].x={unsigned(l-1),0,1}; return; }
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(u);
    }
    void upd(int u,Mat tag){ T[u].x=T[u].x*tag,T[u].tag=T[u].tag*tag; }
    void pushdown(int u){ upd(ls,T[u].tag),upd(rs,T[u].tag),T[u].tag=I; }
    void upd(int u,int l,int r,int ql,int qr,Mat x){
        if(ql<=l&&r<=qr){ upd(u,x); return; }
        pushdown(u);
        if(ql<=mid) upd(ls,l,mid,ql,qr,x);
        if(mid<qr)  upd(rs,mid+1,r,ql,qr,x);
        pushup(u);
    }
    Vec qry(int u,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return T[u].x;
        Vec res{};
        if(ql<=mid) res=qry(ls,l,mid,ql,qr);
        if(mid<qr) res=res+qry(rs,mid+1,r,ql,qr);
        return res;
    }
#undef ls
#undef rs
#undef mid
} sgt;
int n,k,qn,tp,A[MAXN];
map<int,int> pos; int prv[MAXN],mxprv[MAXN];
struct{ int l,r,id; } Q[MAXN]; unsigned ans[MAXN];
map<int,vector<int>> mp1,mp2;
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
    freopen("degree.in","r",stdin);
    freopen("degree.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k>>qn>>tp;
    assert(tp==0);
    RNG(i,1,n) cin>>A[i];
    RNG(i,1,n) prv[i]=pos[A[i]],mxprv[i]=max(mxprv[i-1],prv[i]),pos[A[i]]=i;
    sgt.build(1,1,n);
    RNG(i,1,qn) cin>>Q[i].l>>Q[i].r,Q[i].id=i;
    sort(Q+1,Q+n+1,[](auto x,auto y){ return x.r<y.r; });
    RNG(i,1,n,q=0){
        {
            auto& stk=mp1[A[i]%k];
            if(stk.empty()) stk.push_back(0);
            {
                auto x=I; x.a[2][0]+=1;
                sgt.upd(1,1,n,stk.back()+1,i,x);
            }
            while(stk.size()>1&&A[stk.back()]/k<=A[i]/k){
                auto p=stk.back(); stk.pop_back();
                auto x=I; x.a[2][0]+= A[i]/k-A[p]/k;
                sgt.upd(1,1,n,stk.back()+1,p,x);
            }
            stk.push_back(i);
        }
        {
            auto& stk=mp2[A[i]%k];
            if(stk.empty()) stk.push_back(0);
            while(stk.size()>1&&A[stk.back()]/k>=A[i]/k){
                auto p=stk.back(); stk.pop_back();
                auto x=I; x.a[2][0]+=-A[i]/k+A[p]/k;
                sgt.upd(1,1,n,stk.back()+1,p,x);
            }
            stk.push_back(i);
        }
        {
            auto x=I; x.a[0][1]=1,x.a[2][1]=(unsigned)-i;
            sgt.upd(1,1,n,mxprv[i]+1,i,x);
        }
        while(q<qn&&Q[q+1].r==i){ q++; ans[Q[q].id]=sgt.qry(1,1,n,Q[q].l,i).a[1]; }
    }
    RNG(i,1,qn) cout<<ans[i]<<"\n";
}