// https://oj.uz/problem/view/JOI20_harvest
/*
Main idea based on https://codeforces.com/blog/entry/74871?#comment-593909:
The goal is to create a functional graph with (n + m) vertices.
There are two types of nodes: apple nodes and collector nodes.
There are two types of queries: collector nodes not in a cycle (1)
and collector nodes in a cycle (2).
For the (1) queries, create a segment tree where each node is a
vector containing the heights of every apple node in that range. Each
apple node contributes only log(n) times. Thus, the preparation and
query steps would take n * (log2(n))^2 operations.
For the (2) queries, consider a vertex S as the root of the cycle.
Compute all the first-time T_i that vertex i meets S (if i is in S's
subtree, then it's the second time) for convenience.
For any query (C, T), transform it into queries (1) and (2):
For the (1) part, determine how many vertices can be reached from
C's subtree in that amount of time.
For the (2) part, it becomes (S, T - dist(C, S)).
So basically, all queries are transformed into (S, T).
The length of the cycle is denoted as len.
The answer involves the sum of all (T - T_i) / len + 1 (where T_i <= T).
Sort T so that the (T_i <= T) case is not considered.
The answer is the sum of ((T / len) - (T_i / len) + (T_i % len <= T % len)) for all i.
The modulo part can be easily computed using a fenwick_tree and compression.
Overall : O(n * log2(n) ^ 2)
*/
#include <bits/stdc++.h>
using namespace std;
class segtree_t {
public:
segtree_t *left, *right;
int l, r, m;
vector<int64_t> val;
segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val() {
if (l == r) return;
left = new segtree_t(l, m);
right = new segtree_t(m + 1, r);
}
void Update(int p, int64_t x) {
val.emplace_back(x);
if (l == r) return;
if (p <= m) {
left->Update(p, x);
} else {
right->Update(p, x);
}
}
void Sort() {
if (l == r) return;
sort(val.begin(), val.end());
left->Sort();
right->Sort();
}
int64_t Get(int s, int t, int64_t limit) {
if (l > t || r < s) return 0;
if (s <= l && r <= t) {
return upper_bound(val.begin(), val.end(), limit) - val.begin();
}
return left->Get(s, t, limit) + right->Get(s, t, limit);
}
};
segtree_t *tree;
template <class T>
class fenwick_t {
public:
vector<T> bit;
int n;
fenwick_t(int n = 0) : n(n) {
bit.resize(n + 3, 0);
}
void Update(int pos, T val) {
for (pos++; pos < bit.size(); pos += pos & -pos) {
bit[pos] += val;
}
}
T Get(int pos) {
T res = T(0);
for (pos++; pos > 0; pos -= pos & -pos) {
res += bit[pos];
}
return res;
}
T Get(int l, int r) {
return Get(r) - ((l >= 0) ? Get(l - 1) : T(0));
}
};
const int MAXN = 4e5;
int n, m, l, c;
int a[MAXN], b[MAXN];
int nxt[MAXN];
int64_t dnxt[MAXN];
bool in_cycle[MAXN];
int done[MAXN];
int64_t dcycle[MAXN];
int S[MAXN];
int root[MAXN];
int64_t dS[MAXN];
int64_t cycle_length[MAXN];
int branch[MAXN];
int qa[MAXN];
int64_t qt[MAXN];
int ord[MAXN];
int64_t ans[MAXN];
int cnt[MAXN];
int cur[MAXN];
int64_t sum[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;
int64_t depth[MAXN];
fenwick_t<int> fw[MAXN];
stack<int> st;
vector<int> all_S;
vector<pair<int, int64_t>> adj[MAXN];
vector<int64_t> T[MAXN];
vector<int> which[MAXN];
vector<int64_t> mod[MAXN];
inline int dist(int i, int j) { // counter-clock-wise
return i >= j ? i - j : i + l - j;
}
void build_functional_graph() {
for (int i = 0; i < m; i++) {
int j = lower_bound(a, a + n, b[i]) - a;
if (j == 0) j = n;
j--;
nxt[i + n] = j;
dnxt[i + n] = dist(b[i], a[j]);
}
for (int i = 0; i < n; i++) {
int nxt_time = (a[i] - c) % l;
if (nxt_time < 0) nxt_time += l;
int j = upper_bound(a, a + n, nxt_time) - a;
if (j == 0) j = n;
j--;
dnxt[i] = c + dist(nxt_time, a[j]);
nxt[i] = j;
}
}
void detect_cycles() {
for (int i = 0; i < n + m; i++) {
if (done[i]) continue;
int x = i;
while (done[x] == 0) {
st.emplace(x);
done[x] = 1;
x = nxt[x];
}
if (done[x] == 1) { // cycle
S[x] = x;
all_S.emplace_back(x);
}
while (st.size()) S[st.top()] = S[x], done[st.top()] = 2, st.pop();
}
for (int i : all_S) {
int x = i;
int64_t length = 0;
do {
S[x] = i;
in_cycle[x] = 1;
dcycle[x] = length;
length += dnxt[x];
x = nxt[x];
} while (x != i);
cycle_length[i] = length;
}
}
void dfs(int u) {
tin[u] = ++timer;
for (auto [v, w] : adj[u]) {
depth[v] = depth[u] + w;
dfs(v);
}
tout[u] = timer;
} // [tin[u], tout[u]]
void dfs(int u, int id) {
branch[u] = id;
for (auto [v, w] : adj[u]) {
if (in_cycle[v]) continue;
dS[v] = dS[u] + w;
dfs(v, id);
}
}
void prep() {
for (int i = 0; i < n; i++) {
if (in_cycle[i] && S[i] == nxt[i]) {
nxt[i] = -1;
root[S[i]] = i;
}
}
for (int i = 0; i < n + m; i++) {
if (nxt[i] == -1) continue;
adj[nxt[i]].emplace_back(i, dnxt[i]);
}
set<int> sss;
for (int i : all_S) {
assert(sss.find(root[i]) == sss.end());
sss.emplace(root[i]);
dfs(root[i]);
}
assert(timer == n + m);
tree = new segtree_t(1, n + m);
for (int i = 0; i < m; i++) tree->Update(tin[n + i], depth[n + i]);
tree->Sort();
for (int i = 0; i < n; i++) {
if (in_cycle[i]) dfs(i, i);
}
for (int i = 0; i < m; i++) T[S[i + n]].emplace_back(dS[i + n] + cycle_length[S[i + n]] - dcycle[branch[i + n]]);
for (int i : all_S) {
sort(T[i].begin(), T[i].end());
int64_t len = cycle_length[i];
auto &modulo = mod[i];
for (int64_t j : T[i]) modulo.emplace_back(j % len);
sort(modulo.begin(), modulo.end());
modulo.resize(unique(modulo.begin(), modulo.end()) - modulo.begin());
which[i].resize(T[i].size());
for (int j = 0; j < which[i].size(); j++) {
which[i][j] = lower_bound(modulo.begin(), modulo.end(), T[i][j] % len) - modulo.begin();
}
fw[i] = fenwick_t<int>(modulo.size());
}
}
int64_t solve1(int x, int64_t time_left) {
int64_t lowest_depth = time_left + depth[x];
return tree->Get(tin[x], tout[x], lowest_depth);
}
void two_pointer(int i, int64_t time_left) {
auto &j = cnt[i];
while (j < which[i].size()) {
if (T[i][j] > time_left) return;
sum[i] += T[i][j] / cycle_length[i];
fw[i].Update(which[i][j], +1);
j++;
}
}
int64_t solve2(int x, int64_t time_left) {
two_pointer(x, time_left);
int64_t len = cycle_length[x];
int64_t res = -sum[x] + 1ll * (time_left / len) * cnt[x];
int limit = upper_bound(mod[x].begin(), mod[x].end(), time_left % len) - mod[x].begin() - 1;
res += fw[x].Get(limit);
return res;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> l >> c;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
build_functional_graph();
detect_cycles();
prep();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
cin >> qa[i] >> qt[i], qa[i]--;
}
for (int i = 0; i < q; i++) {
ans[i] += solve1(qa[i], qt[i]);
}
for (int i = 0; i < q; i++) {
if (!in_cycle[qa[i]]) continue;
qt[i] -= dcycle[qa[i]];
qa[i] = S[qa[i]];
}
iota(ord, ord + q, 0);
sort(ord, ord + q, [&](int i, int j) {
return qt[i] < qt[j];
});
for (int z = 0; z < q; z++) {
int i = ord[z];
if (!in_cycle[qa[i]]) continue;
ans[i] += solve2(qa[i], qt[i]);
}
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
