#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll M = 200'010; ll base = 1<<19; ll nxt = 1,cnt; vector<vector<ll>> adj(M), tadj(M), gscc(M); vector<vector<pair<ll, ll>>> g(M); vector<ll> post_order, vis(M), scc(M), ile(1), root(M), dep(M), pre(M), post(M), Tree(2*base); void update(ll x, ll val) { x += base; Tree[x] += val; x/=2; while(x > 0) { Tree[x] = Tree[x+x] + Tree[x+x+1]; x/=2; } } ll query(ll a, ll b) { a+=base-1; b+=base+1; ll ans = 0; while(a/2 != b/2) { if(a%2==0) ans += Tree[a+1]; if(b%2==1) ans += Tree[b-1]; a/=2; b/=2; } return ans; } void post_dfs(ll v) { if(vis[v]) return; vis[v] = 1; for(auto u : adj[v]) post_dfs(u); post_order.push_back(v); } void trans_dfs(ll v) { scc[v] = nxt; cnt++; for(auto u : tadj[v]) if(!scc[u]) trans_dfs(u); } struct zapyt { ll v, t, idx; }; vector<zapyt> queries(M); vector<ll> ans(M); void dfs(ll v) { pre[v] = ++nxt; for(auto[u,c] : g[v]) { if(scc[u]==scc[root[v]]) continue; dep[u] = dep[v] + c; root[u] = root[v]; dfs(u); } post[v] = nxt; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,m,l,c; cin >> n >> m >> l >> c; vector<ll> emp(n); for(ll i=0; i<n; ++i) cin >> emp[i]; vector<ll> Trees(m); for(ll i=0; i<m; ++i) cin >> Trees[i]; ll q; cin >> q; queries.resize(q); for(ll i=0; i<q; ++i) { ll v, t; cin >> v >> t; queries[i] = {v-1,t,i}; } vector<ll> poprz(m); vector<vector<ll>> my_tres(n); auto dist = [&](ll a, ll b) { if(a <= b) return b-a; return l - (a-b); }; for(ll i=0; i<m; ++i) { ll it = lower_bound(emp.begin(), emp.end(), Trees[i]) - emp.begin(); it--; if(it < 0) it = n-1; poprz[i] = it; my_tres[it].push_back(dist(emp[it], Trees[i])); } for(ll i=0; i<n; ++i) sort(my_tres[i].begin(), my_tres[i].end()); ll iterator = 1%n; auto dist_emp = [&](ll x, ll y) { if(x <= y) return emp[y] - emp[x]; else return l - (emp[x] - emp[y]); }; for(ll i=0; i<n; ++i) { while(dist_emp((iterator+1)%n, i) >= c) iterator = (iterator+1)%n; adj[iterator].push_back(i); g[iterator].push_back({i, dist_emp(iterator, i)}); tadj[i].push_back(iterator); } for(ll i=0; i<n; ++i) post_dfs(i); reverse(post_order.begin(), post_order.end()); for(auto v : post_order) { if(!scc[v]) { cnt = 0; trans_dfs(v); ile.push_back(cnt); nxt++; } } nxt = 1; for(ll i=0; i<n; ++i) { if(ile[scc[i]] > 1) { root[i] = i; dfs(i); } } vector<pair<ll, ll>> zap2; for(ll i=0; i<q; ++i) { auto[v,t,idx] = queries[i]; if(ile[scc[v]] > 1) continue; zap2.push_back({t + dep[v], i}); } vector<vector<ll>> subTree(n); for(ll i=0; i<n; ++i) { for(auto x : my_tres[i]) { zap2.push_back({dep[i] + x, -i-1}); subTree[root[i]].push_back(dep[i] + x); } } sort(zap2.begin(), zap2.end()); for(auto[czas, type] : zap2) { if(type<0) { type*=-1; type--; update(pre[type], 1); } else { ans[type] = query(pre[queries[type].v], post[queries[type].v]); } } vector<ll> vis(n); vector<pair<ll, ll>> next(n); for(ll i=0; i<n; ++i) { for(auto[u,c] : g[i]) { if(scc[u]==scc[i]) next[i] = {u,c}; } } vector<vector<ll>> myq(n); for(auto[v,t,idx] : queries) myq[v].push_back(idx); for(ll start=0; start<n; ++start) { if(ile[scc[start]]==1 || vis[start]) continue; ll okres = 0; ll v = start; ordered_set<ll> os; ll dodane = 0; do { vis[v] = 1; for(auto x : subTree[v]) os.insert(okres + x); okres += next[v].second; v = next[v].first; } while(v!=start); if(os.empty()) continue; do { // cout << v << ": "; for(auto x : os) cout << x + dodane << " "; cout << "\n"; for(ll idx : myq[v]) { ll czas = queries[idx].t; /*ll ile = max(0LL, czas-(*os.rbegin())-dodane) / okres; czas -= ile*okres; ans[idx] = ile * os.size() + os.order_of_key(czas-dodane+1);*/ for(auto x : os) { ll val = x + dodane; if(val <= czas) ans[idx] += (czas-val)/okres + 1; } } auto[u,c] = next[v]; for(auto x : subTree[v]) os.erase(x-dodane); for(auto x : subTree[v]) os.insert(x+okres-dodane); dodane -= c; v = u; } while(v!=start); } for(ll i=0; i<q; ++i) cout << ans[i] << "\n"; return 0; }