#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
std::mt19937 rng(23);
struct set {
struct node {
node* lc = nullptr;
node* rc = nullptr;
int wei = rng();
int siz = 0;
i64 x = 0;
node() {}
node(i64 x_) : siz(1), x(x_) {}
};
node* root = nullptr;
int size(node* v) { return v ? v->siz : 0; }
void pull(node*& v) {
if (!v) {
return;
}
v->siz = size(v->lc) + size(v->rc) + 1;
}
void merge(node*& v, node* lv, node* rv) {
if (!lv || !rv) {
v = lv ? lv : rv;
return;
}
if (lv->wei > rv->wei) {
merge(lv->rc, lv->rc, rv);
v = lv;
} else {
merge(rv->lc, lv, rv->lc);
v = rv;
}
pull(v);
}
void split_by_x(node* v, node*& lv, node*& rv, i64 x) {
if (!v) {
lv = nullptr;
rv = nullptr;
return;
}
if (v->x <= x) {
split_by_x(v->rc, v->rc, rv, x);
lv = v;
} else {
split_by_x(v->lc, lv, v->lc, x);
rv = v;
}
pull(lv);
pull(rv);
}
void insert(i64 x) {
node* a;
node* b;
node* nd = new node(x);
split_by_x(root, a, b, x);
merge(root, a, nd);
merge(root, root, b);
}
int lower_bound(i64 x) {
node* a;
node* b;
split_by_x(root, a, b, x);
int res = size(a);
merge(root, a, b);
return res;
}
std::vector<i64> extract() {
std::vector<i64> res;
auto dfs = [&](auto&& self, node* v) -> void {
if (!v) {
return;
}
self(self, v->lc);
res.emplace_back(v->x);
self(self, v->rc);
};
dfs(dfs, root);
return res;
}
void clear() {
auto dfs = [&](auto&& self, node*& v) -> void {
if (!v) {
return;
}
self(self, v->lc);
self(self, v->rc);
free(v);
};
dfs(dfs, root);
}
int size() {
return size(root);
}
void merger(node*& v, node* lv, node* rv) {
if (!lv || !rv) {
v = lv ? lv : rv;
return;
}
if (lv->wei > rv->wei) {
node* a;
node* b;
split_by_x(rv, a, b, lv->x);
merger(lv->lc, lv->lc, a);
merger(lv->rc, lv->rc, b);
v = lv;
} else {
node* a;
node* b;
split_by_x(lv, a, b, rv->x);
merger(rv->lc, a, rv->lc);
merger(rv->rc, b, rv->rc);
v = rv;
}
pull(v);
}
void merge_sets(const set& rhs) {
merger(root, root, rhs.root);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
i64 L, C;
std::cin >> N >> M >> L >> C;
std::vector<i64> A(N), B(M);
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
for (int i = 0; i < M; ++i) {
std::cin >> B[i];
}
int Q;
std::cin >> Q;
std::vector<std::array<i64, 2>> qrys(Q);
for (int i = 0; i < Q; ++i) {
i64 V, T;
std::cin >> V >> T;
--V;
qrys[i] = {V, T};
}
std::vector<int> f(N);
std::vector<i64> dis(N);
for (int i = 0; i < N; ++i) {
i64 tim = (A[i] - C % L + L) % L;
auto it = std::upper_bound(A.begin(), A.end(), tim);
f[i] = (it == A.begin() ? N - 1 : int(it - A.begin() - 1));
dis[i] = C + (it == A.begin() ? tim + L - A[N - 1] : tim - A[f[i]]);
}
debug(f);
debug(dis);
std::vector<int> on_cycle(N, true);
std::vector<int> deg(N);
for (int i = 0; i < N; ++i) {
deg[f[i]] += 1;
}
std::queue<int> que;
for (int i = 0; i < N; ++i) {
if (deg[i] == 0) {
que.emplace(i);
}
}
std::vector<int> ord;
while (!que.empty()) {
auto v = que.front();
que.pop();
ord.emplace_back(v);
on_cycle[v] = false;
if (--deg[f[v]] == 0) {
que.emplace(f[v]);
}
}
debug(on_cycle);
std::vector<i64> cycle_len(N, -1);
std::vector<i64> cycle_loc(N, -1);
std::vector<int> cycle_start(N, -1);
for (int i = 0; i < N; ++i) {
if (!on_cycle[i] || cycle_start[i] != -1) {
continue;
}
i64 len = 0;
int v = i;
do {
cycle_start[v] = i;
cycle_loc[v] = len;
len += dis[v];
v = f[v];
} while (v != i);
cycle_len[v] = len;
}
debug(cycle_start);
debug(cycle_loc);
debug(cycle_len);
std::vector<i64> need_fruit(M);
std::vector<i64> start_fruit(M);
for (int i = 0; i < M; ++i) {
auto it = std::upper_bound(A.begin(), A.end(), B[i]);
need_fruit[i] = (it == A.begin() ? N - 1 : int(it - A.begin() - 1));
start_fruit[i] = (it == A.begin() ? B[i] + L - A[N - 1] : B[i] - A[need_fruit[i]]);
}
debug(need_fruit);
debug(start_fruit);
std::vector<std::vector<int>> have_fruit(N);
for (int i = 0; i < M; ++i) {
have_fruit[need_fruit[i]].emplace_back(i);
}
std::reverse(ord.begin(), ord.end());
std::vector<int> cycle_enter(N, -1);
std::vector<i64> cycle_enter_need(N, -1);
for (auto i : ord) {
if (on_cycle[f[i]]) {
cycle_enter[i] = f[i];
cycle_enter_need[i] = dis[i];
} else {
cycle_enter[i] = cycle_enter[f[i]];
cycle_enter_need[i] = cycle_enter_need[f[i]] + dis[i];
}
}
debug(cycle_enter);
debug(cycle_enter_need);
std::vector<i64> ans(Q);
std::vector<std::vector<int>> ask(N);
for (int i = 0; i < Q; ++i) {
ask[qrys[i][0]].emplace_back(i);
}
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < N; ++i) {
if (!on_cycle[i]) {
adj[f[i]].emplace_back(i);
}
}
debug(__LINE__);
std::vector<set> sets(N);
auto dfs1 = [&](auto&& self, int v) -> void {
for (auto u : adj[v]) {
self(self, u);
sets[v].merge_sets(sets[u]);
}
for (auto i : have_fruit[v]) {
sets[v].insert(start_fruit[i] + cycle_enter_need[need_fruit[i]]);
}
debug(v, sets[v].extract());
for (auto i : ask[v]) {
auto t = qrys[i][1];
ans[i] = sets[v].lower_bound(cycle_enter_need[v] + t);
}
};
std::vector<std::vector<i64>> add_later(N);
for (int i = 0; i < N; ++i) {
if (!on_cycle[i] && on_cycle[f[i]]) {
dfs1(dfs1, i);
for (auto j : sets[i].extract()) {
add_later[f[i]].emplace_back(j);
}
sets[i].clear();
}
}
debug(__LINE__);
adj.assign(N, {});
for (int i = 0; i < N; ++i) {
if (on_cycle[i] && i != cycle_start[i]) {
adj[f[i]].emplace_back(i);
}
}
auto dfs2 = [&](auto&& self, int v) -> void {
debug(v);
for (auto u : adj[v]) {
self(self, u);
sets[v].merge_sets(sets[u]);
}
if (v != cycle_start[v]) {
for (auto i : have_fruit[v]) {
sets[v].insert(cycle_len[cycle_start[v]] - cycle_loc[v] + start_fruit[i]);
}
for (auto i : add_later[v]) {
sets[v].insert(cycle_len[cycle_start[v]] - cycle_loc[v] + i);
}
} else {
for (auto i : have_fruit[v]) {
sets[v].insert(start_fruit[i]);
}
for (auto i : add_later[v]) {
sets[v].insert(i);
}
}
if (v != cycle_start[v]) {
for (auto i : ask[v]) {
auto t = qrys[i][1];
ans[i] += sets[v].lower_bound(cycle_len[cycle_start[v]] - cycle_loc[v] + t);
}
}
};
for (int i = 0; i < N; ++i) {
if (on_cycle[i] && i == cycle_start[i]) {
dfs2(dfs2, i);
std::vector<int> cyc;
{
int v = i;
do {
cyc.emplace_back(v);
v = f[v];
} while (v != i);
}
debug(i, sets[i].extract());
auto vec = sets[i].extract();
std::vector<std::array<i64, 2>> askall;
for (auto v : cyc) {
for (auto q : ask[v]) {
auto t = qrys[q][1] - cycle_loc[v];
askall.push_back({t, q});
// for (auto j : sets[i].extract()) {
// if (j <= t) {
// ans[q] += (t - j) / cycle_len[i] + 1;
// }
// }
}
}
i64 clen = cycle_len[i];
std::sort(askall.begin(), askall.end());
int p = 0;
int cnt = 0;
i64 sum = 0;
set mset;
for (auto[t, q] : askall) {
while (p != int(vec.size()) && vec[p] <= t) {
cnt += 1;
sum += vec[p] / clen;
mset.insert(vec[p] % clen);
++p;
}
ans[q] += (t / clen) * cnt - sum + mset.lower_bound(t % clen);
}
}
}
for (int i = 0; i < Q; ++i) {
std::cout << ans[i] << '\n';
}
return 0;
}
