#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;
}
