记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
int read() {
	int f = 1, k = 0;//f是正负号,k用来将字符转换成数字
	char c = getchar();//读入一个字符 
	//非数字 
	while(c < '0' || c > '9'){//读到空格后
		c = getchar();//读入空格等。 
	}
	//数字 
	while( c >= '0' && c<= '9'){
		k =k * 10 + c - '0';
		c = getchar();//一位一位读入数字 
	}
	return f * k;
	
}
const int N=5e5+100,M=2e6+100;
int n,m,d,q,a[N],b[N],bb[N],val[N];
bool flag[N];
inline void deal_bb(){
	sort(bb+1,bb+1+m);
	int num=unique(bb+1,bb+1+m)-bb-1;
	flag[1]=1;
	for(re int i=2;i<=num;i++){
		flag[i]=1;
		for(re int j=i-1;j>=1;j--){
			int x=bb[i];
			while(x>bb[j]) x/=d;
			if(x==bb[j]){
				flag[i]=0;
				break;
			}
		}
	}
	m=0;
	for(re int i=1;i<=num;i++) if(flag[i]) b[++m]=bb[i];
}
struct tree{int l,r,sum;}t[M];
#define lson o<<1
#define rson o<<1|1
inline void build(int o,int l,int r){
	t[o].l=l,t[o].r=r;
	if(l==r) return void(t[o].sum=val[l]);
	int mid=(l+r)>>1;
	build(lson,l,mid),build(rson,mid+1,r);
	t[o].sum=(t[lson].sum|t[rson].sum);
}
inline int query(int o,int l,int r){
	if(t[o].l==l and t[o].r==r) return t[o].sum;
	int mid=(t[o].l+t[o].r)>>1;
	if(r<=mid) return query(lson,l,r);
	else if(l>mid) return query(rson,l,r);
	else return (query(lson,l,mid)|query(rson,mid+1,r)); 
}
int p[70];
signed main(){
	cin>>n>>m>>d>>q;
	for(re int i=1;i<=n;i++) a[i]=read();
	for(re int i=1;i<=m;i++) bb[i]=read();
	deal_bb();
	int mx=0;
	for(re int i=1;i<=n;i++){
		for(re int j=1;j<=m;j++){
			int x=a[i];
			while(x>b[j]) x/=d;
			if(x==b[j]){
				val[i]=(1<<(j-1));//这个a 可以变成的b 状态压缩储存 
				mx=max(mx,j-1);
				break;
			}
		}
	}
	if(b[1]==0){
		while(q--){
			int l,r;
			l=read(),r=read();
			cout<<1<<endl;
		}
	}
	p[0]=1;
	for(re int i=1;i<=mx;i++) p[i]=(p[i-1]<<1);
	build(1,1,n);
	int l,r;
	while(q--){
		l=read(),r=read();
		int ans=query(1,l,r);
		int now=1,cnt=0;
		for(re int i=0;i<=mx and p[i]<=ans;i++) if(ans&p[i]) cnt++;
		printf("%lld\n",cnt);
	}
}