#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pl = pair<ll,ll>; using pii = pair<int,int>; using tpl = tuple<int,int,int>; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 6e5 + 5; ll a[mn], b[mn], ans[mn], N, M, L, C; vector<pair<ll,int>> qry[mn]; namespace sunGraph { vector<pair<int,ll>> adj[mn], rev[mn], line, queries; bool marked[mn], inCycle[mn]; int processed[mn], countQuery[mn], root, pivot; ll treeDepth[mn], backEdge, sumCycle, base; vector<int> cycle; vector<ll> wait; void addEdge (int a, int b, ll w) { // cout << a << " " << b << " " << w << "\n"; adj[a].emplace_back(b, w); rev[b].emplace_back(a, w); } bool detectCycle (int u) { if (marked[u]) { // found cycle int lastErase = 0; while (lastErase != u) { tie(lastErase, backEdge) = line.back(), line.pop_back(); cycle.push_back(lastErase), sumCycle += backEdge; inCycle[lastErase] = 1; } return reverse(all(cycle)), 1; } marked[u] = 1; for (auto [v, w] : adj[u]) { line.emplace_back(u, w); if (detectCycle(v)) return 1; line.pop_back(); } return 0; } void dfsTree (int u) { processed[u] = 1, countQuery[u] = u > N; for (auto [v, w] : rev[u]) { if (processed[v]) continue; treeDepth[v] = treeDepth[u] + w; dfsTree(v); countQuery[u] += countQuery[v]; } } void processTree (int u) { processed[u] = 2; for (auto [v, w] : rev[u]) if (processed[v] < 2) processTree(v); // process virtual leaf nodes if (u > N) { base += treeDepth[u] / sumCycle; wait.push_back(treeDepth[u] % sumCycle); } // get the queries for (auto [T, idx] : qry[u]) { if (inCycle[u]) { if (u != root) ans[idx] += countQuery[u]; ll shift = (u == root ? 0 : treeDepth[pivot] - treeDepth[u] + backEdge); ans[idx] += countQuery[root] * ((T - shift) / sumCycle) + countQuery[root]; queries.emplace_back((T - shift) % sumCycle, idx); } else { ans[idx] += countQuery[u]; } } } // solve for the connected component containing `source` void solveComponent (int source) { // re-initialize data sumCycle = backEdge = base = 0; line.clear(), cycle.clear(), queries.clear(), wait.clear(); detectCycle(source); // form a rooted tree pivot = cycle[1 % cycle.size()]; dfsTree(root = cycle[0]), processTree(root); // some pre-process sort(all(wait), greater<ll>()); sort(all(queries)); for (auto [T, idx] : queries) { while (wait.size() && wait.back() <= T) wait.pop_back(); ans[idx] -= base + (int)wait.size(); } } bool needProcess (int u) { return !processed[u]; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M >> L >> C; for (int i = 1; i <= N; i++) cin >> a[i], a[i + N] = a[i] + L; for (int i = 1; i <= M; i++) cin >> b[i]; // build sun-graph ll CmodL = C % L; for (int i = 1; i <= N; i++) { int nxt = upper_bound(a, a + 2 * N + 1, a[i + N] - CmodL) - a - 1; sunGraph::addEdge(i, nxt, C - CmodL + a[i + N] - a[nxt]); } // add virtual vertices for apples for (int i = 1; i <= M; i++) { int start = upper_bound(a, a + 2 * N + 1, b[i] + L) - a - 1; sunGraph::addEdge(i + N, start - (start > N ? N : 0), b[i] + L - a[start]); } // preprocess queries int Q; cin >> Q; for (int i = 0; i < Q; i++) { int V; ll T; cin >> V >> T; qry[V].emplace_back(T, i); } // solve for (int i = 1; i <= N + M; i++) if (sunGraph::needProcess(i)) sunGraph::solveComponent(i); for (int i = 0; i < Q; i++) cout << ans[i] << "\n"; return 0; }