#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 = 4e5 + 5; int a[mn], b[mn], n, m, C, L; // this namespace solves the graph-related subproblem namespace sunGraph { vector<pair<int,ll>> adj[mn], rev[mn]; ll comp[mn], cycleID[mn], nxtWeight[mn], num[mn], sz[mn], root[mn], cycleLength[mn]; ll treeDist[mn], preSum[mn], sumCycle[mn]; bool inCycle[mn], vist[mn]; void addEdge (int a, int b, ll weight) { cout << a << " " << b << " " << weight << "\n"; adj[a].emplace_back(b, weight); rev[b].emplace_back(a, weight); } ll detectCycle (int u) { static vector<pair<int,int>> line; static int counter = 0; if (vist[u]) { // found cycle vector<pair<int,int>> cycle; while (cycle.empty() || cycle.back().first != u) cycle.push_back(line.back()), line.pop_back(); reverse(all(cycle)); ll sumWeight = 0; for (auto [node, weight] : cycle) { cycleID[node] = ++counter, nxtWeight[counter] = weight; inCycle[node] = 1, cycleLength[counter] = cycle.size(); } for (auto [node, weight] : cycle) nxtWeight[++counter] = weight, sumWeight += weight; line.clear(); return sumWeight; } vist[u] = 1; for (auto [v, weight] : adj[u]) { line.emplace_back(u, weight); if (ll tmp = detectCycle(v)) return tmp; line.pop_back(); } return 0; } void colorComponent (int u, int color) { if (comp[u]) return; comp[u] = color; for (auto [v, weight] : adj[u]) if (!comp[v]) colorComponent(v, color); for (auto [v, weight] : rev[u]) if (!comp[v]) colorComponent(v, color); } void dfsTree (int u, int r) { static int timeDfs = 0; num[u] = ++timeDfs, sz[u] = 1, root[u] = r; for (auto [v, weight] : rev[u]) { if (inCycle[v]) continue; dfsTree(v, r); treeDist[v] = treeDist[u] + weight, sz[u] += sz[v]; } } void process() { // detect cycles and mark connected components int counter = 0; for (int i = 1; i <= n + m; i++) { // cout << "what!?" << endl; if (comp[i]) continue; sumCycle[++counter] = detectCycle(i); colorComponent(i, counter); cout << "sc " << sumCycle[counter] << "\n"; } // process trees for (int i = 1; i <= n; i++) if (inCycle[i]) dfsTree(i, i); // run prefix sums for (int i = 1; i <= 2 * n; i++) preSum[i] = preSum[i - 1] + nxtWeight[i]; } // check if node c is in the subtree of st bool inTree (int st, int c) { return num[st] <= num[c] && num[c] < num[st] + sz[st]; } // calculate the distance of going from a node with cycleID "from" to "to" ll goCycle (int from, int to) { if (from == to) return 0; if (from > to) to += cycleLength[to]; return preSum[to - 1] - preSum[from - 1]; } // the number of visiting time if we start from source, and want to reach the target ll visitTime (int source, int target, ll travelTime) { // cout << comp[source] << " " << comp[target] << " "; if (comp[source] != comp[target]) return 0; if (inCycle[target]) { ll length = treeDist[source] + goCycle(cycleID[root[source]], cycleID[target]); if (travelTime < length) return 0; return 1 + (travelTime - length) / sumCycle[comp[source]]; } if (!inTree(target, source)) return 0; return travelTime >= treeDist[source] - treeDist[target]; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); // 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]; // cout << "coordinate: "; // for (int i = 1; i <= 2 * n; i++) cout << a[i] << " "; // cout << "\n"; // build edge int Cmod = C % L, Cdiv = C / L; for (int i = n + 1; i <= 2 * n; i++) { // cout << "searching " << a[i] - Cmod << "\n"; int j = upper_bound(a + 1, a + 1 + 2 * n, a[i] - Cmod) - a - 1; int weight = C + (a[i] - Cmod - a[j]); sunGraph::addEdge(i - n, j - (j <= n ? 0 : n), weight); } // build virtual nodes for each apple tree for (int i = 1; i <= m; i++) { int j = upper_bound(a + 1, a + 1 + 2 * n, b[i] + L) - a - 1; sunGraph::addEdge(n + i, j - (j <= n ? 0 : n), b[i] + L - a[j]); } sunGraph::process(); int q; cin >> q; while (q--) { // cout << "bro "; int V; ll T, ans = 0; cin >> V >> T; for (int i = 1; i <= m; i++) ans += sunGraph::visitTime(n + i, V, T); cout << ans << "\n"; } return 0; }