代码：

#include<bits/stdc++.h>
using namespace std;

#define PII pair<int,int>
typedef long long LL;
typedef unsigned long long ULL;
LL read() {
    char c=getchar(); LL sum=0,flag=1;
    while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
    while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
    return sum*flag;
}

const int N=5e5+10,M=1e6+10;
int n,m,d,q;
LL a[N],b[N];
int nxt[70],p[70];
struct node {
    int id,l,r;
}s[M];
int tr[N];
int ans[M];

int cmp(node x,node y) {
    return x.l<y.l;
}

int lowbit(int x) {
    return x&(-x);
}

void modify(int nd,int x) {
    if(!nd) return ;
    for(int i=nd;i<=n;i+=lowbit(i)) tr[i]+=x;
}

int query(int nd) {
    int ans=0;
    for(int i=nd;i;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

int main(){
    n=read(); m=read(); d=read(); q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    map<LL,int> pd;
    for(int i=1;i<=m;i++) {
        b[i]=read();
        pd[b[i]]=1;
    }
    sort(b+1,b+1+m);
    for(int i=m;i>=1;i--) {
        LL x=b[i];
        while(x) {
            x/=d; if(pd[x]) {b[i]=-1; break;}
        }
    }
    map<LL,int> id;    
    for(int i=1;i<=m;i++) if(b[i]!=-1) id[b[i]]=i;
    for(int i=n;i>=1;i--) {
        if(id.count(a[i])) a[i]=id[a[i]];
        else {
            while(a[i]) {
                a[i]/=d;
                if(id.count(a[i])) {a[i]=id[a[i]];break;}
            }            
        }
        nxt[i]=p[a[i]]; p[a[i]]=i;
    }
    for(int i=1;i<=n;i++) if(p[a[i]]==i&&a[i]) modify(i,1);
    for(int i=1;i<=q;i++) {
        int l=read(),r=read();
        s[i]={i,l,r};
    }
    sort(s+1,s+1+q,cmp);
    int np=0;
    for(int i=1;i<=q;i++) {
        while(np<s[i].l) {
            if(a[np]) {
                modify(np,-1);
                modify(nxt[np],1);
            }
            np++;
        }
        ans[s[i].id]=query(s[i].r)-query(s[i].l-1);
    }

    for(int i=1;i<=q;i++) cout<<ans[i]<<endl;

    return 0;
}
/*
离线树状数组即可
移动左端点
*/