#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6;
int a[N],b[N];
struct node{
    bool m[100];
    int l,r;
}tree[N<<2];
set<int>nowb;
int nowa[N];
void pushup(int x)
{
    for(int i=0;i<70;i++)tree[x].m[i]=0;
    for(int i=0;i<70;i++)tree[x].m[i]=tree[x<<1].m[i]|tree[x<<1|1].m[i];
}
void build(int x,int l,int r)
{
    tree[x].l=l;
    tree[x].r=r;
    if(l==r)
    {
        if(nowa[l]) tree[x].m[nowa[l]]=1;
        return;
    }
    int mid=l+(r-l)/2;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
bool ans[N];
void ask(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r)
    {
        for(int i=0;i<70;i++)ans[i]|=tree[x].m[i];
        return;
    }
    int mid=tree[x].l+(tree[x].r-tree[x].l)/2;
    if(l<=mid)ask(x<<1,l,r);
    if(r>mid)ask(x<<1|1,l,r);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m,d,p;cin>>n>>m>>d>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    sort(b+1,b+1+m);
    for(int i=m;i>=1;i--)
    {
        int res=b[i];
        while(b[i]!=0)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(b[i]==b[j])
                {
                    res=b[j];
                }
            }
            b[i]/=d;
        }
        nowb.insert(res);
    }
    m=0;
    for(auto num:nowb)b[++m]=num;
    for(int i=1;i<=n;i++)
    {
        int tmp=a[i];
        while(tmp!=0)
        {
            for(int j=1;j<=m;j++)
            {
                if(b[j]==tmp)
                {
                    nowa[i]=b[j];
                    break;
                }
            }
            if(nowa[i])break;
            tmp/=d;
        }
    }
    build(1,1,n);
    while(p--)
    {
        memset(ans,0,sizeof(ans));
        int x,y;cin>>x>>y;
        ask(1,x,y);
        int res=0;
        for(int i=1;i<=m;i++)if(ans[b[i]])res++;
        cout<<res<<"\n";
    }
    return 0;
}