#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()) struct SparseBIT { map<ll,int> cached; ll limit; SparseBIT (ll limit) : limit(limit) {} ll p (ll k) { return k & -k; } void update (ll pos, int val) { for (; pos <= limit; pos += p(pos)) cached[pos] += val; } int preSum (ll pos) { int ans = 0; for (; pos; pos -= p(pos)) ans += (cached.count(pos) ? cached[pos] : 0); return ans; } int query (ll L, ll R) { return preSum(R) - preSum(L - 1); } }; const int mn = 4e5 + 5; const ll MX = 2e14; ll a[mn], b[mn], N, M, L, C; namespace sunGraph { vector<pair<int,ll>> adj[mn], rev[mn], queries[mn], line; int num[mn], sz[mn], root, tail, timeDfs; ll weight[mn], result[mn], sumCycle, backEdge; vector<int> nodeList; bool vis[mn], process[mn], inCycle[mn]; bool detectCycle (int u) { if (vis[u]) { // found cycle tie(root, backEdge) = line.back(), tail = u; int lastNode = 0; while (lastNode != u) { assert(line.size()); lastNode = line.back().first; sumCycle += line.back().second; line.pop_back(); inCycle[lastNode] = true; } return true; } vis[u] = true; for (auto [v, curWeight] : adj[u]) { line.emplace_back(u, curWeight); if (detectCycle(v)) return true; line.pop_back(); } return false; } void dfsPrepare (int u) { process[u] = true, sz[u] = 1, num[u] = ++timeDfs; nodeList.push_back(u); for (auto [v, curWeight] : rev[u]) { if (process[v]) continue; weight[v] = weight[u] + curWeight; dfsPrepare(v); sz[u] += sz[v]; } } void solveComponent (int u) { if (process[u]) return; // component that contains u is already processed line.clear(); // preprocess graph if (!detectCycle(u)) { cout << "No cycle found" << endl; exit(0); } dfsPrepare(root); sort(all(nodeList), [&] (int a, int b) { return weight[a] < weight[b]; }); int szComp = nodeList.size(); // prepare queries vector<tuple<ll,int,int>> subtreeQuery; // type-1 query vector<pair<ll,int>> rootQuery; // type-2 query for (int u : nodeList) { for (auto [idx, T] : queries[u]) { if (!inCycle[u]) subtreeQuery.emplace_back(T + weight[u], u, idx); else if (u == root) rootQuery.emplace_back(T, idx); else { // general inCycle case ll delay = weight[tail] - weight[u] + backEdge; if (delay <= T) rootQuery.emplace_back(T - delay, idx); subtreeQuery.emplace_back(T + weight[u], u, idx); } } } sort(all(subtreeQuery), greater<tuple<ll,int,int>>()); sort(all(rootQuery), greater<pair<ll,int>>()); // helper data structures and functions SparseBIT tree(szComp), modTree(MX); ll counter = 0, sumWeightDiv = 0; function<void(void)> subtreeProcess = [&]() { ll bound; int node, idx; tie(bound, node, idx) = subtreeQuery.back(); subtreeQuery.pop_back(); result[idx] += tree.query(num[node], num[node] + sz[node] - 1); // if (idx == 0) cout << "subtree " << idx << " " << node << " " << bound << " r" << tree.query(num[node], num[node] + sz[node] - 1) << endl; }; function<void(void)> rootProcess = [&]() { ll T; int idx; tie(T, idx) = rootQuery.back(); rootQuery.pop_back(); result[idx] += (T / sumCycle + 1) * counter; result[idx] -= sumWeightDiv; result[idx] -= modTree.query(T % sumCycle + 1, MX); // if (idx == 0) cout << "root " << idx << " " << T << endl; }; // sweep line for (int u : nodeList) { if (u <= N) continue; // process subtree queries while (subtreeQuery.size() && get<0>(subtreeQuery.back()) < weight[u]) subtreeProcess(); // process root queries while (rootQuery.size() && rootQuery.back().first < weight[u]) rootProcess(); // update node u counter++, sumWeightDiv += (weight[u] / sumCycle); tree.update(num[u], 1), modTree.update(weight[u] % sumCycle, 1); } // process remaining queries while (subtreeQuery.size()) subtreeProcess(); while (rootQuery.size()) rootProcess(); // reset data line.clear(), nodeList.clear(); root = sumCycle = backEdge = timeDfs = 0; } void addEdge (int a, int b, ll weight) { adj[a].emplace_back(b, weight); rev[b].emplace_back(a, weight); } }; int main() { ios::sync_with_stdio(0); cin.tie(0); // read input 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], b[i] += L; // graph edges ll CMod = C % L, CDiv = C / L; for (int i = N + 1; i <= 2 * N; i++) { int nextNode = upper_bound(a + 1, a + 2 * N + 1, a[i] - CMod) - a - 1; ll weight = CDiv * L + a[i] - a[nextNode]; sunGraph::addEdge(i - N, nextNode - (nextNode > N ? N : 0), weight); } // virtual nodes' edges for (int i = 1; i <= M; i++) { int nextNode = upper_bound(a + 1, a + 2 * N + 1, b[i]) - a - 1; ll weight = b[i] - a[nextNode]; sunGraph::addEdge(N + i, nextNode - (nextNode > N ? N : 0), weight); } // read queries int Q; cin >> Q; for (int i = 0; i < Q; i++) { int V; ll T; cin >> V >> T; sunGraph::queries[V].emplace_back(i, T); } // solve for each component and output answer for (int i = 1; i <= N; i++) sunGraph::solveComponent(i); for (int i = 0; i < Q; i++) cout << sunGraph::result[i] << "\n"; return 0; }