#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500005;
ll a[N], b[65], temp[65], f[N][20];
int c[N];
ll query(int l, int r) {
	int q = log2(r - l + 1);
	return f[l][q] | f[r - (1 << q) + 1][q];
}
int main() {
	int n, m, q;
	ll d;
	scanf("%d %d %lld %d", &n, &m, &d, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%lld", &b[i]);
	}
	sort(b + 1, b + m + 1);
	m = unique(b + 1, b + m + 1) - (b + 1);
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		ll now = b[i];
		bool flag;
		while (true) {
			for (int j = 1; j < i; j++) {
				if (b[j] == now) {
					flag = false;
					break;
				}
			}
			if (now == 0) {
				flag = true;
				break;
			}
			now /= d;
		}
		if (flag) {
			cnt++;
			temp[cnt] = b[i];
		}
	}
	m = cnt;
	for (int i = 1; i <= m; i++) {
		b[i] = temp[i];
	}
	for (int i = 1; i <= n; i++) {
		ll now = a[i];
		c[i] = -1;
		while (true) {
			for (int j = 1; j <= m; j++) {
				if (b[j] == now) {
					c[i] = j;
					break;
				}
			}
			if (now == 0) {
				break;
			}
			now /= d;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (c[i] == -1) {
			f[i][0] = 0;
		} else {
			f[i][0] = (1LL << c[i]);
		}
	}
	for (int j = 1; j <= 19; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			f[i][j] = f[i][j - 1] | f[i + (1 << (j - 1))][j - 1];
		}
	}
	for (int l, r, i = 1; i <= q; i++) {
		scanf("%d %d", &l, &r);
		printf("%d\n", __builtin_popcountll(query(l, r)));
	}
	return 0;
}